給定一個?n×m 的二維整數數組，用來表示一個迷宮，數組中只包含?0?或?1，其中?0?表示可以走的路，1?表示不可通過的墻壁。
最初，有一個人位于左上角?(1,1)處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置。
請問，該人從左上角移動至右下角?(n,m) 處，至少需要移動多少次。
數據保證?(1,1) 處和?(n,m) 處的數字為?0，且一定至少存在一條通路。
輸入格式
第一行包含兩個整數?n?和?m。
接下來?n?行，每行包含?m?個整數（00?或?11），表示完整的二維數組迷宮。
輸出格式
輸出一個整數，表示從左上角移動至右下角的最少移動次數。
數據范圍
1≤n,m≤100
輸入樣例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
輸出樣例：
8思路：從起始點出發，每次找它旁邊的能走的點（上下左右四個方向），然后再從新找到的點找旁邊能走的點，依次類推，直到找到終點為止，這里我們用一個隊列去實現，先將起點入隊，然后當隊列不為空的時候，每次取出隊頭的點，找出隊頭旁邊的點，將旁邊能走的點（且第一次找到）入隊，這樣就能一直找找到終點。
BFS就是把這一層全部搜完才會搜下一層，因此它第一次搜到的點就是該點離起始點最近的時候，適合用來解決求最小步數，最少操作幾次等最短路問題。
?找的順序如下圖所示
可以看到在圖上的例子里面，我們找了八次找到了終點，也就是終點到起點的距離為8。
如何實現找出隊頭旁邊的點：
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; //用向量表示點走四個方向后的變化，分別是上下左右while(q.size()){PII t=q.front(); //得到隊頭q.pop(); //刪掉隊頭，和上面的代碼加起來就是取出隊頭for(int i=0;i<4;i++) //隊頭的點依次走四個方向{int x=t.first+dx[i];int y=t.second+dy[i];//點在邊界內且點可以走且點是第一次被找到if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1){d[x][y]=d[t.first][t.second]+1; //每次找的是它的上下左右的點，且不會找已經走過的點，所以找到的點離起點的距離就又遠了1q.push({x,y}); //把這個新找到的點放進隊伍中}}}
用dx和dy數組表示上下左右四個方向移動后點坐標的變化，這里的坐標(x,y)表示的是x行y列，向上就是x-1，y不變，我們把它放進dx和dy的第一個元素里，寫為-1和0?
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; //用向量表示點走四個方向后的變化，分別是上下左右四個方向的變化如下圖所示：?
示例代碼：?
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;typedef pair<int,int> PII; //這個主要是方便隊列存放點的坐標，所以需要一對int
const int N =100;
int n,m;
int g[N][N]; //存儲地圖
int d[N][N]; //存儲每一個點到起點的距離int bfs()
{queue<PII> q;memset(d,-1,sizeof(d)); //初始全部設為-1，表示全沒走過d[0][0]=0; //起始點到起點的距離為0q.push({0,0}); //第一個點入隊int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; //用向量表示點走四個方向后的變化，分別是上下左右while(q.size()){PII t=q.front(); //得到隊頭q.pop(); //刪掉隊頭，和上面的代碼加起來就是取出隊頭for(int i=0;i<4;i++) //隊頭的點依次走四個方向{int x=t.first+dx[i];int y=t.second+dy[i];//沿著這個方向走，點在邊界內，并且這個點可以走(g[x][y]==0)，這個點還沒有走過（d[x][y]==-1，第一次搜到的點才是最短距離）if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1){d[x][y]=d[t.first][t.second]+1; //每次找的是它的上下左右的點，且不會找已經走過的點，所以找到的點離起點的距離就又遠了1q.push({x,y}); //把這個新找到的點放進隊伍中}}}return d[n-1][m-1]; //輸出到右下角的點（終點）的最短距離
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}cout<<bfs()<<endl;return 0;
}
