公主被BEelzebub feng5166绑架，我们的英雄Ignatius必须拯救我们漂亮的公主。现在他进入了feng5166的城堡。城堡是一个大型的迷宫。为了简单地解决这个问题，我们假设迷宫是一个N * M的二维数组，左上角是（0,0），右下角是（N-1，M-1）。Ignatius进入（0,0），feng5166房间的门是（N-1，M-1），这是我们的目标。这是一些规则：
1.Ignatius只能向四个方向（上，下，左，右）移动，一步一秒。步骤定义如下：如果当前位置为（x，y），则在步骤之后，Ignatius只能站在（x-1，y），（x + 1，y），（x，y-1）或（X，Y + 1）。
2.数组标有一些字符和数字，定义如下
.：Ignatius可以走路的地方。
X：这个地方是一个陷阱，Ignatius不能走在上面。
你的任务是给出Ignatius达到目标位置所需的最小秒数。您可以假设起始位置和目标位置永远不会成为陷阱。
测试数据有多组
每个测试样例以包含两个数字N和M（2 <= N <= 100,2 <= M <= 100）的行开始，这表示迷宫的大小。
然后是N * M二维矩阵，描述整个迷宫。
输入格式见样例输入
对于每个测试样例
你应该输出“God please help our poor hero.”。 如果Ignatius无法到达目标位置，或者你应该输出“It takes n seconds to reach the target position.”（n是最小秒数）
#include<iostream> #include<queue> #include<cstring> using namespace std; #define INF 0x7f int array[INF][INF]; int visit[INF][INF]; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; int N,M; class node { public: int x,y,sec; node() { x=y=-1; sec=0; } node(int x1,int y1,int sec1) { x=x1; y=y1; sec=sec1; } }; int BFS() {//向右y正，向下x正 queue<node>Q; node start(0,0,0); Q.push(start); visit[0][0]=1; int tag=0; while(!Q.empty()) { if(Q.front().x==N-1&&Q.front().y==M-1) { tag=1; break; } for(int i=0;i<4;i++) { int nx=Q.front().x; int ny=Q.front().y; nx+=dx[i]; ny+=dy[i]; if(nx>=0&&nx<=N-1&&ny>=0&&ny<=M-1) { if(array[nx][ny]==1&&visit[nx][ny]==0) { visit[nx][ny]=1; node p(nx,ny,Q.front().sec+1); Q.push(p); } } } Q.pop(); } if(tag==1) return Q.front().sec; else return 0; } int main() { while(cin>>N>>M) { memset(array,0,sizeof(array)); memset(visit,0,sizeof(visit)); string str; for(int i=0;i<N;i++) { cin>>str; for(int j=0;j<M;j++) { if(str[j]==‘.‘) array[i][j]=1; else if(str[j]==‘X‘) array[i][j]=0; } } int result=BFS(); if(result==0) cout<<"God please help our poor hero."<<endl; else cout<<"It takes "<<result<<" seconds to reach the target position."<<endl; } return 0; }
原文：https://www.cnblogs.com/SZU-DS-wys/p/12182970.html