python/C++课程/待整理知识/BFS算法/10X10走迷宫.cpp

//BFS算法入门
//https://blog.csdn.net/qq_42757965/article/details/82019460
//好文！！！！ 

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn=205;
char ch[maxn][maxn];
int dis[maxn][maxn];//做为标记如果这个点搜索过了标记为1,没有搜索过标记为0；
int d[4][2]={1,0,-1,0,0,1,0,-1};//能走的四个方向；
int n,m;
int edx,edy,enx,eny;
struct stu
{
    int x;
    int y;
    int step;
}A,B;
void bfs(int x,int y)
{
    queue<stu> que;
    A.x=x;
    A.y=y;
    A.step=0;
    dis[x][y]=1;
    que.push(A);
    int cnt=-1;
    while(!que.empty())
    {
 
        A=que.front();//把队列的顶端元素取出，
        que.pop();
        if(A.x==enx&&A.y==eny)//如果找到了终点那么搜索就结束了。
        {
            cnt=A.step;
            break;
        }
        for(int i=0;i<4;i++)//一个节点可以走的四个方向，
        {
            B.x=A.x+d[i][0];
            B.y=A.y+d[i][1];
            if(B.x>=0&&B.x<n&&B.y>=0&&B.y<m&&dis[B.x][B.y]==0&&ch[B.x][B.y]!='#')//判断这一步能不能走；
            {
                if(ch[B.x][B.y]=='x') B.step=A.step+2;
                else B.step=A.step+1;
                dis[B.x][B.y]=1;//这个点已经走过，所以要标记下来；
                que.push(B);//把走的这个节点放进队列里面；
            }
        }
    }
   if(cnt == -1) puts("Poor ANGEL has to stay in the prison all his life.");
	else
        printf("%d\n", cnt);
 
}
int main()
{
    while(~scanf("%d %d",&n,&m ))
    {
        A.step=0;
        B.step=0;
        memset(dis,0,sizeof(dis));
        for(int i=0;i<n;i++)
            scanf("%s",ch[i]);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(ch[i][j]=='a')
                {
                    edx=i;
                    edy=j;
                }
                if(ch[i][j]=='r')
                {
                    enx=i;
                    eny=j;
                }
            }
        }
        bfs(edx,edy);
    }
    return 0;
}