题解 P2199 【最后的迷宫】
Blue_wonders · · 题解
bfs暴力枚举做法（不简单易懂你打我！）
萌新没发过几次题解，也是尽量写的详细一些，求关照
这题有点坑，不不不，是坑死人！
先给各位大佬排几个坑（被坑了三回）
- 先输入奖杯，再输入哈利坐标
- 注意奖杯和哈利同坐标的情况，记得特判
- 哈利能看八个方向，但只能走四个方向
- 哈利看八个方向只要没有墙就能无限看，一直能看到边界
排坑完毕然后是我的做法
先输入地图 然后只要有输入，就不停进行bfs跑图 广搜一定是最短，只要找到能看到奖杯的点就退出输出
代码在下面（附详解）
#include<iostream> #include<cstring> #include<cstdio>//头文件不用说 using namespace std; int kx[4]={1,-1,0,0}; int ky[4]={0,0,1,-1};//这俩是行走方向 int lx[8]={-1,-1,-1,0,0,1,1,1}; int ly[8]={0,1,-1,-1,1,-1,0,1};//这俩是观察的八个方向 int map[5001][5001];//存地图 int vis[5001][5001];//存是否走过 int m,n; struct h{//用结构建体方便bfs int x,y,dep; }; h p[100000];//建立队列 int judge(int x,int y,int ex,int ey){//判断是否能够看到奖杯 if(x==ex&&y==ey)return 1;//特判：奖杯是否与这个点重合 for(int i=0;i<=7;i++){//8个方向分别判断 int x0=x+lx[i],y0=y+ly[i]; while(x0>0&&x0<=m&&y0>0&&y0<=n&&map[x0][y0]==0){//只要不超边界，看不到墙就一直延一个方向搜索 if(x0==ex&&y0==ey)return 1;//如果延伸后看得到就返回1 x0=x0+lx[i]; y0=y0+ly[i];//不是就继续延伸 } } return 0;//如果8个方向判断完毕都看不到就返回0 } int bfs(int sx,int sy,int ex,int ey){//bfs搜索 p[0]=(h){sx,sy,0};//队列首加入 int head=0,tail=1; while(tail>head){//只要队列有东西就运行 int x=p[head].x,y=p[head].y,step=p[head].dep; head++;//取出一个成员 if(judge(x,y,ex,ey)==1)return step;//判断是否能看到，1代表能看到就输出当前步数，0代表看不到就继续进行 for(int i=0;i<=3;i++){//搜索可以走的地方 int x0=x+kx[i],y0=y+ky[i]; if(x0>0&&x0<=m&&y0>0&&y0<=n&&vis[x0][y0]==0&&map[x0][y0]==0){//判断新点是否在边界里，是否是墙，是否走过 p[tail]=(h){x0,y0,step+1};//加入队列 vis[x0][y0]=1;//标记走过的点 tail++; } } } return -1;//如果所有点都看不见那么输出-1代表看不到 } int main(){//先看主程序 cin>>m>>n; for(int i=1;i<=m;i++){//输入X为1代表不能走，O为0代表能走 string s;//字符串读入 cin>>s; for(int j=0;j<n;j++){ if(s[j]=='X')map[i][j+1]=1; else map[i][j+1]=0; } } int sx,sy,ex,ey; cin>>ex>>ey>>sx>>sy;//注意先读入奖杯坐标，注意！ while(sx!=0||sy!=0||ex!=0||ey!=0){//若都为零那么代表结束 memset(vis,0,sizeof(vis));//每次清空vis数组 vis[sx][sy]=1; //先把原坐标标记 int a=bfs(sx,sy,ex,ey);//进行bfs搜索 if(a!=-1)cout<<a;//输出步数，若是-1代表看不到 else cout<<"Poor Harry"; cout<<endl; cin>>ex>>ey>>sx>>sy;//下一组输入 } return 0; }感谢能看我的题解！