PTA迷宫探路

迷宫探路"/>

PTA迷宫探路

本题目要求读入2个整数A和B，表示A行B列的迷宫，迷宫中有障碍点。给定起始点和终止点，要求从起始点到终止点的最小步数。

输入格式:

输入n组如下的数：
输入2个整数A和B，表示A行B列的迷宫，然后输入一个整数C，表示障碍点数，再依次输入C个障碍点的坐标（x，y），最后输入起始点和终止点的坐标（xs，ys）和(xe，ye)。

输出格式:

针对每组数，输出从起始点到终止点的最小步数。若无法达到，则输出“Not arrive”。

 注意两种情况：入口和出口不重合，重合

#include <bits/stdc++.h>
using namespace std;
int aa[25][25];//地图
int flag[25][25];//走过的路径标记
int x00, y00;//迷宫起点
int x11, y11;//迷宫出口int fx[] = { 0, 0, -1, 1 };
int fy[] = { -1, 1, 0, 0 };int a, b, c;//行列大小、障碍物数量int sum = 1 << 30;//假设一个很大的路径步数stack<pair<int,int>>p;//用于存放路径（x,y）的栈void bfs(int x,int y)//广搜   
{if (x == x11 && y == y11)//如果符合条件，return;{sum = min(sum, (int)p.size());//利用栈的size，取得最小路径步数return;}for (int i = 0; i < 4; i++)//循环判断，某个点的周边四个点是否为合法路径{int xx = x + fx[i], yy = y + fy[i];//得到周围点的坐标if (aa[xx][yy] == -1)continue;//如果是障碍物，跳过，判断下一个点if (xx < 0 || xx >= a || yy < 0 || yy >= b)continue;//出界，跳过if (flag[xx][yy])continue;//已经走过，跳过flag[xx][yy] = 1;//满足上述所有条件，判断此点为合法点，标记为1，表示第一次到达p.push({ xx,yy });//压入路径栈bfs(xx, yy);//递归判断，此点周围四个点是否合法p.pop();//这里只能是从出口return回来的，表示pop出口点，flag[xx][yy] = 0;//回溯，将出口重新标记为没有走过的点}
}int main()
{int t;cin >> t;while (t--){cin >> a >> b;cin >> c;for (int i = 1; i <= c; i++){int cx, cy;cin >> cx;cin >> cy;aa[cx][cy] = -1;}cin >> x00 >> y00;cin >> x11 >> y11;sum = 1 << 30;//刷新sum的值为一个很大的数p.push({ x00,y00 });//压入入口点flag[x00][y00] = 1;//标记入口点bfs(x00,y00);//开始递归判断while (p.size())//清空路径栈{p.pop();}memset(aa, 0, sizeof(aa));//清空地图和标记memset(flag, 0, sizeof(flag));if (sum < 9999)//如果没有到达出口的路径，则sum没有被更新过，是一个很大的数cout << sum - 1;elsecout << "Not arrive";if (t > 0)cout << endl;}return 0;
}