信息
- ID
- 993
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 3
- 标签
- 递交数
- 49
- 已通过
- 27
- 上传者
#include
using namespace std;
int r,c,dx[]= {-1,0,0,1},dy[]= {0,-1,1,0};
char a[45][45];
bool vis[45][45];
struct Point {
int x,y,step;
};
queue<Point> q;
bool check(int x,int y) { // 检查该点(x,y)是否可以通行以及是否未走过
return x>=1&&y>=1&&x<=r&&y<=c&&!vis[x][y]&&a[x][y]=='.';
}
int bfs() {
vis[1][1]=1;
q.push((Point) {
1,1,1
}); // 点(1,1)为什么花了1步我不理解,0步是WA,1步是AC
while(q.size()) {
Point now=q.front();
q.pop();
for(short i=0; i<4; i++) {
int nx=now.x+dx[i],ny=now.y+dy[i];
if(check(nx,ny)) {
if(nx==r&&ny==c)return now.step+1;
vis[nx][ny]=1;
q.push((Point) {
nx,ny,now.step+1
});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>r>>c;
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
cin>>a[i][j];
cout<<bfs();
return 0;
}