双语题解·广搜bfs

1、Python

a=[int(i) for i in input().split()]
n=a[0]
m=a[1]
road=[]
for i in range(n):
    s=input()
    road.append([])
    for j in s:
        road[i].append(j!='#')
q=[]
dir=((1,0),(0,1),(-1,0),(0,-1))
vis=[[0 for i in range(m)] for i in range(n)]
q.append((0,0,1))
vis[0][0]=1
s=2147483647
while(len(q)):
    tup=q.pop(0)
    if tup[0]==n-1 and tup[1]==m-1:
        s=min(s,tup[2])
    else:
        for i in dir:
            nx=tup[0]+i[0];ny=tup[1]+i[1]
            if nx>=0 and nx<n and ny>=0 and ny<m and not vis[nx][ny] and road[nx][ny]:
                vis[nx][ny]=1
                q.append((nx,ny,tup[2]+1))
if s==2147483647:
    print(-1)
else:
    print(s)

2、C++

#include<iostream>
#include<queue>
using namespace std;
int s=2147483647,x,y;
bool map[50][50],vis[50][50];
struct node{
    int x,y,step;
};
void bfs(){
    queue<node>q;
    q.push({1,1,1});
    vis[1][1]=1;
    while(!q.empty()){
        node f=q.front();
        q.pop();
        if(f.x==x&&f.y==y){
            s=min(f.step,s);
        }else{
            if(f.x-1&&map[f.x-1][f.y]&&!vis[f.x-1][f.y]){q.push({f.x-1,f.y,f.step+1});vis[f.x-1][f.y]=1;}
            if(f.y-1&&map[f.x][f.y-1]&&!vis[f.x][f.y-1]){q.push({f.x,f.y-1,f.step+1});vis[f.x][f.y-1]=1;}
            if(x-f.x&&map[f.x+1][f.y]&&!vis[f.x+1][f.y]){q.push({f.x+1,f.y,f.step+1});vis[f.x+1][f.y]=1;}
            if(y-f.y&&map[f.x][f.y+1]&&!vis[f.x][f.y+1]){q.push({f.x,f.y+1,f.step+1});vis[f.x][f.y+1]=1;}
        }
    }
}
int main(){
    cin>>x>>y;
    for(int i=1;i<=x;i++)for(int j=1;j<=y;j++){
        char c;
        cin>>c;
        map[i][j]=c=='.';
    }
    bfs();
    cout<<(s==2147483647?-1:s)<<endl;
    return 0;
}