题目
5
4 2 1 4
01010
11100
11111
10011
10001
out
no
思路
回溯法
设置maze数组保存数据
设置mark数组记录是否走过该路径
设置route栈记录走过的地方(回溯
设置mv数组来表示步数
当栈不为空的时候走遍栈顶的每一条路线,直到遇见mark是0且maze是0的路线,否则返回上一级,直到栈空or找到路为止
代码
#include<iostream>
using namespace std;
struct STACK{int x,y,d;};
struct MOVE{int a,b;};
char maze[100][100];
int mark[100][100];
STACK route[100*100];
MOVE mv[8];
int top;
int n;
int getmazepath(int x1, int y1, int x2, int y2)
{
int now_x,now_y,dir,next_x,next_y,t;
if(maze[x1][y1] != '0' || maze[x2][y2] != '0')
return 1;
route[0].x = x1;
route[0].y = y1;
route[0].d = -1;
top = 1;
mark[x1][y1] = 1;
while(top > 0)
{
now_x = route[--top].x;
now_y = route[top].y;
dir = route[top].d;
while(dir < 7)
{
next_x = now_x + mv[++dir].a;
next_y = now_y + mv[dir].b;
if(next_x < 0 || next_y < 0 || next_x >= n || next_y >= n )
continue;
if(next_x == x2 && next_y == y2)
{
// for(t = 0; t < top; t++)
// printf("%3d%3d%3d;",route[t].x,route[t].y,route[t].d);
// printf("%3d%3d%3d;",i,j,k);
// printf("%3d%3d%3d;\n",x2,y2,-1);
return 0;
}
if(maze[next_x][next_y] == '0' && mark[next_x][next_y] == 0)
{
mark[next_x][next_y] = 1;
route[top].x = now_x;
route[top].y = now_y;
route[top++].d = dir;
now_x = next_x;
now_y = next_y;
dir = -1;
}
}
}
return 1;
}
int main()
{
cin >> n;
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
for(int i = 0; i < n; i++)
for(int j = 0; j < n ; j++)
{
mark[i][j] = 0;
cin >> maze[i][j];
}
// for(int i = 0; i < n; i++)
// {
// for(int j = 0; j < n; j++)
// cout << maze[i][j];
// cout << endl;
// }
mv[0].a = -1; mv[0].b = 0;
mv[1].a = -1; mv[1].b = 1;
mv[2].a = 0; mv[2].b = 1;
mv[3].a = 1; mv[3].b = 1;
mv[4].a = 1; mv[4].b = 0;
mv[5].a = 1; mv[5].b = -1;
mv[6].a = 0; mv[6].b = -1;
mv[7].a = -1; mv[7].b = -1;
if(getmazepath(x1,y1,x2,y2))
cout << "no" << endl;
else
cout << "yes" << endl;
}