PTA 迷宫探路

迷宫探路"/>

PTA 迷宫探路

题目详情 - 7-8 迷宫探路 (20 分) (pintia)

虽然它只是要最短路径或者最终是否到达终点，但是它坑点很多。首先它是多组输入，每一组输入找完之后，迷宫和查询是否访问的数组，已经初始化的最小步数也要更新，否则就是上一次走迷宫剩下的，并且这个样例与你是否重新初始化没有关系，它还是会输出和输出样例一样的最小步数。

然后还要另一个点就是查询是否能够到达终点，我们就要在主函数里面dfs过后去看最小步数min是否更新，已经更新，则证明已经到达终点，否则不能到达终点。

然后就是代码了，注释的话，就不写了，只要注意到上面所说的几个点，就能过了。

#include<stdio.h>
int n,a,b,c,min=999999,sx,sy,ex,ey;
int s[1005][1005];
int vis[1005][1005];
int moves[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x,int y,int step)
{if(x==a-1&&y==b-1){if(step<min)min=step;return;}for(int i=0; i<4; i++){int nx=x+moves[i][0];int ny=y+moves[i][1];if(nx<0||nx>=a||ny<0||ny>=b) continue;if(vis[nx][ny]==0&&s[nx][ny]==0){vis[nx][ny]=1;dfs(nx,ny,step+1);vis[nx][ny]=0;}}return;
}
int main()
{scanf("%d",&n);while(n--){scanf("%d %d",&a,&b);for(int i=0;i<a;i++){for(int j=0;j<b;j++){s[i][j]=0;vis[i][j]=0;}}min=999999;scanf("%d",&c);int x,y;for(int i=1; i<=c; i++){scanf("%d %d",&x,&y);s[x][y]=1;}scanf("%d %d",&sx,&sy);scanf("%d %d",&ex,&ey);vis[sx][sy]=1;dfs(sx,sy,0);if(min!=999999)printf("%d\n",min);elseprintf("Not arrive\n");}return 0;
}