题解 P2298 【Mzc和男家丁的游戏】
Sun_Qixuan · · 题解
相信各位同志发现，这一道题是一个标准的BFS
进入正题......
#include <bits/stdc++.h>
using namespace std;
char mp[2000][2000];int vis[2000][2000],next[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//定义地图，vis是记录走过的格子。
//next是走下一步的坐标变化
int cnt,flag=0;//定义步数和判断是否到达终点的变量
struct Node//结构体，定义一个节点
{
int x,y,s;//定义这一个节点的坐标(x,y)，以及走到这个节点的步数。
Node(int _x,int _y,int _s)
{
x=_x;y=_y;s=_s;
}//这里只是一种简洁的方法，也可以直接在BFS（）里赋值
};
int BFS()//广搜函数
{
queue <Node> v;int n,m,sx,sy;cin>>n>>m;
//定义一个STL库里的队列，和地图长宽以及起始地点
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>mp[i][j];//输入地图
if(mp[i][j]=='m')
{
sx=i;sy=j;//如果发现了起点那就将起始地点变量赋值
}
}
Node temp_cci(sx,sy,0);v.push(temp_cci);//将起始地点压入队列
while(!v.size()==0)
{
Node head=v.front();v.pop();//将这一个节点记录到head里，准备往下搜索
if(mp[head.x][head.y]=='d')//如果head已经是终点
{
cnt=head.s;flag=1;break;//那就给这两个变量赋值，并break
}
for(int i=0;i<4;i++)//往下搜索
{
int tx=head.x+next[i][0];//往一个方向的x坐标变化
int ty=head.y+next[i][1];//往一个方向的y坐标变化
//结成一个点
if(tx<0||ty<0||tx>=n||ty>=m||vis[tx][ty]==1||mp[tx][ty]=='#') continue;
//如果超出边界，点已经被走过，是障碍，全部跳过(毫不留情)
Node temp(tx,ty,head.s+1);v.push(temp);vis[tx][ty]=1;//如果没有被跳过，那就把点压入队列，准备下一次搜索
}
}
}
int main()
{
BFS();
if(flag) cout<<cnt;//如果找到了终点，输出步数
else cout<<"No Way!";//没有？输出No Way(注意N和W要大写)
}