走迷宮(ybt1252
#include <bits/stdc++.h>
using namespace std;
const int N=110;
char g[N][N];//存儲迷宮
int n,m;
typedef pair<int,int> PII;
PII q[N*N];//隊列 記錄坐標
int d[N][N];//記錄最少步數(shù)
int bfs() {
??? int hh=0,tt=0;
?? ?q[hh]={0,0}; //入口
?? ?memset(d,-1,sizeof d);//把d這個存儲空間上的所有值初始化-1
?? ?d[0][0]=1;
?? ?int dx[4]={-1,0,1,0};
?? ?int dy[4]={0,1,0,-1};
?? ?while(hh<=tt) {
?? ??? ?PII/*auto*/ t=q[hh++];
?? ??? ?for(int i=0;i<4;i++) {
?? ??? ??? ?int a=t.first+dx[i];
?? ??? ??? ?int b=t.second+dy[i];
?? ??? ??? ?if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='.'&&d[a][b]==-1) {
?? ??? ??? ??? ?d[a][b]=d[t.first][t.second]+1;
?? ??? ??? ??? ?q[++tt]={a,b};
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?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;
}