[C++知识库]C++利用DFS算法求迷宫通关最短步骤以及路径

在算出最短的路径的基础上，利用DFS回溯的特性增/删路径，以此来实现对于路径的记录。

PS：最初想通过定义string类型数据来记录路径，但是在回溯删除多余路径时会出现问题（运用函数删除string类型最末尾数据的时候，如果最末尾数据为汉字时会由于数据类型的缘故删除失败出现乱码……求大神的解决方案）

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int a[100][100]={0},v[100][100]={0};
//string b;
char b[100][3];
int n=0;
//string c; 
char c[100][3];
int temp=9999;
int xEnd,yEnd;
int count;
void dfs(int x,int y,int step)
{
	if(x==xEnd && y==yEnd)
	{
		
		if(temp>step)
		{
			//cout << c << endl;
			temp=step;
			for(int i=0;i<n;i++)
			{
				strcpy(c[i],b[i]);
			 } 
			 count=n;
			/*for(int k=0;k<temp;k++)
			{
				strcpy(c[k],b[k]);
			}*/
			//c=b;
			//cout << c << endl;
			return ;
		}
	}
	
	if(a[x-1][y]==1 && v[x-1][y]==1)
	{
		v[x-1][y]=2;
		//b+="上";
		strcpy(b[n++],"上");
		dfs(x-1,y,step+1);
		v[x-1][y]=1;
		strcpy(b[--n],"");
		//b=b.substr(0,b.length()-3);
		//cout<<b<<endl;
		//b.erase(b.end()-1);
	}
	if(a[x+1][y]==1 && v[x+1][y]==1)
	{
		v[x+1][y]=2;
		//b+="下"; 
		strcpy(b[n++],"下");
		dfs(x+1,y,step+1);
		v[x+1][y]=1;
		strcpy(b[--n],"");
		//b=b.substr(0,b.length()-1);
		//cout<<b<<endl;
		//b.erase(b.end()-3);
	}
	if(a[x][y-1]==1 && v[x][y-1]==1)
	{
		v[x][y-1]=2;
		//b+="左"; 
		strcpy(b[n++],"左");
		dfs(x,y-1,step+1);
		v[x][y-1]=1;
		strcpy(b[--n],"");
		//b=b.substr(0,b.length()-1);
		//cout<<b<<endl;
		//b.erase(b.end()-3);
	}
	if(a[x][y+1]==1 && v[x][y+1]==1)
	{
		v[x][y+1]=2;
		//b+="右"; 
		strcpy(b[n++],"右");
		dfs(x,y+1,step+1);
		v[x][y+1]=1;
		strcpy(b[--n],"");
		//b-="右";
		//b=b.substr(0,b.length()-1);
		//cout<<b<<endl;
		//b.erase(b.end()-3);
	}
	
	/*else if((x==1&&y==0)||(x==0&&y==1))
	{
		v[0][0]=1;
	}*/
} 
int main()
{
	int m,n;
	cin >> m >> n ;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin >> a[i][j] ;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			v[i][j]=1 ;
		}
	}
	int xStart,yStart;
	cin >> xStart >> yStart ;
	cin >> xEnd >> yEnd ;
	v[xStart][yStart]=2;
	dfs(xStart,yStart,0);
	if(temp==9999)cout<<"没有答案";
	else
	{
		cout << "最短步数" << temp << endl;
		for(int k=0;k<count;k++)
		{
			cout << c[k];
		}
	}
	return 0;
}