7-26 走迷宫 (10 分)
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入格式:
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C <500)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用‘.’表示，有障碍物的格子用‘#’表示。
迷宫左上角和右下角都是‘.’。
输出格式:
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
输入样例:
5 5 ..### #.... #.#.# #.#.# #.#..
输出样例:
9
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char s[500][500];
int n,m,ans,min0;
int i,j;
struct node{
int x,y,step;
};
queue<node>q;
void bfs(){
int i;
s[0][0]='#';
node q1;
q1.x=0;
q1.y=0;
q1.step=1;
q.push(q1);
while(!q.empty()){
node q2=q.front();
q.pop();
for(i=0;i<4;i++){
int xx=q2.x+dx[i];
int yy=q2.y+dy[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='.'){
s[xx][yy]='#';
node q3;
q3.x=xx;
q3.y=yy;
q3.step=(q2.step+1);
if(xx==n-1&&yy==m-1){
min0=q3.step;
return;
}
else{
q.push(q3);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%s",s[i]);
}
bfs();
printf("%d",min0);
return 0;
}