题目844. 走迷宫题目描述给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。最初有一个人位于左上角 (1,1) 处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问该人从左上角移动至右下角 (n,m) 处至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。输入第一行包含两个整数 n 和 m。接下来 n 行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。输出输出一个整数表示从左上角移动至右下角的最少移动次数。数据范围1 ≤ n, m ≤ 100时空限制1s / 64MB输入样例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代码1#includeiostream#includecstringusingnamespacestd;typedefpairint,intPII;constintMaxn10010,Maxm10010;intn,m;intg[Maxn][Maxm];intd[Maxn][Maxm];PII q[Maxn*Maxm];inthh,tt;intbfs(){memset(d,-1,sizeofd);d[0][0]0;q[0]{0,0};intdx[4]{-1,0,1,0},dy[4]{0,1,0,-1};while(hhtt){// 队列不空autotq[hh];// 取出队头元素for(inti0;i4;i){intxt.firstdx[i],yt.seconddy[i];if(x0xny0ymg[x][y]0d[x][y]-1){d[x][y]d[t.first][t.second]1;q[tt]{x,y};}}}returnd[n-1][m-1];}intmain(){scanf(%d%d,n,m);for(inti0;in;i){for(intj0;jm;j){scanf(%d,g[i][j]);}}intresbfs();printf(%d\n,res);return0;}代码2#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,m,g[N][N],sx,sy,ex,ey,dx[5]{0,1,0,-1},dy[5]{1,0,-1,0},dis[N][N];queuePIIq;voidbfs(){q.push({sx,sy});memset(dis,-1,sizeofdis);dis[sx][sy]0;while(!q.empty()){PII tq.front();q.pop();for(inti0;i4;i){intxt.firstdx[i],yt.seconddy[i];if(x0xny0ymdis[x][y]-1!g[x][y]){dis[x][y]dis[t.first][t.second]1;q.push({x,y});}}}}intmain(){cinnm;for(inti0;in;i)for(intj0;jm;j)cing[i][j];exn-1,eym-1;bfs();coutdis[ex][ey];return0;}结果