#2#3#4#5#11#13#14#15#16#17#19 TLE
#12#20 WA
代码如下
#include<iostream>
#include<cstring>
#define N 20
using namespace std;
int n,m,stx,sty,edx,edy; //startx,starty,endx,endy
int map[N][N]; //存图
pair<int,int> Prev[N][N]; //存该坐标下一个坐标
int dx[4]={0,-1,0,1}; //优先顺序:左上右下
int dy[4]={-1,0,1,0};
int flag; //是否有解
void dfs(int x,int y)
{
if(x==edx && y==edy)//如果有解
{
flag=1;//改变标记
int x2=stx,y2=sty;
while(x2!=edx || y2!=edy)//输出路径过程
{
printf("(%d,%d)",x2,y2);
printf("->");
int t1=x2,t2=y2;
x2=Prev[t1][t2].first;
y2=Prev[t1][t2].second;
}
printf("(%d,%d)",edx,edy);
cout<<endl;
return ;//回溯
}
for(int i=0;i<4;i++)
{
int xn=x+dx[i],yn=y+dy[i];
// cout<<xn<<"-----"<<yn<<"-----"<<endl; 调试
if(map[xn][yn] && xn>0 && xn<=m && yn>0 && yn<=n)
{ //符合条件则可以走
Prev[x][y]={xn,yn}; //存储该点的下一个点的坐标
map[xn][yn]=0;
dfs(xn,yn); //递归dfs
Prev[x][y]={0,0}; //回溯
map[xn][yn]=1;
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>map[i][j];
}
}
map[stx][sty]=0; //初始化
cin>>stx>>sty>>edx>>edy;
dfs(stx,sty);
if(!flag) cout<<"-1"<<endl;//无解输出-1
return 0;
}