题目： 小明抄答案

题目描述

有一次上数学课，老师布置了课堂作业。小明在写作业时睡着了。他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：“你现在位于迷宫的左上角，迷宫的右下角有数学作业的答案。你只能上下左右走，但你放心，我没有耍你，迷宫是一定能走得通的。”小明很想拿到答案，但他太笨了，所以找来了会编程的你，叫你帮他找到答案。他需要知道走出迷宫的最少步数（起点格子也计算在内）。

输入格式

第一行包含两个整数m和n，分别表示迷宫的行数和列数。

接下来的m行，每行n个字符，代表整个迷宫。空地用“.”表示，有障碍物的格子用“#”表示（不包含引号）。迷宫的左上角和右下角都是“.”。

输出格式

输出包含一个整数，表示小明找到答案的最少步数。

数据范围与提示

对于 100%的数据，满足：1 ≤ n,m ≤ 50。

输入输出样例

样例1

输入样例 复制

5 5

..###

#....

#.#.#

#.#.#

#.#..

输出样例 复制

9

#include <bits/stdc++.h>
using namespace std;
int m,n;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int G[55][55],vis[55][55];
int sum;
string s;
struct node{
	int x,y;
}q[2510];
void bfs() {
	if(m==1&&n==1) {
		sum=1;
		return;
	}
	memset(vis,0,sizeof(vis));
	int f,t;
	f=t=1;
	q[t++]=(node){1,1};
	vis[1][1]=1;
	while(f!=t) {
		node u=q[f++];
		for(int i=0;i<4;i++) {
			int nx=u.x+dx[i];
			int ny=u.y+dy[i];
			if(nx<1||ny<1||nx>m||ny>n) continue;
			if(G[nx][ny]) continue;
			if(vis[nx][ny]) continue;
			q[t++]=(node){nx,ny};
			vis[nx][ny]=1;
		}
		sum++;
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++) {
		cin>>s;
		for(int j=1;j<=m;j++) {
			G[i][j]=(s[j-1]=='#'?1:0);
		}
	}
	bfs();
	cout<<sum;
    return 0;
}