1407: 【例】【基础】走出迷宫的最少步数

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：18 解决：9

题目描述

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

输入

第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)
接下来是R行，每行C个字符，代表整个迷宫。空地格子用'.'表示，有障碍物的格子用'#'表示。迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

样例输入 复制 

5 5
..###
#....
#.#.#
#.#.#
#.#..

样例输出 复制 

9

提示


#include<bits/stdc++.h>
using namespace std;
#define N 110
char a[N][N];
int b[N][N];
int n,m;
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int cnt=0;
void dfs(int x,int y,int f){
	b[x][y]=f;
	int tx,ty;
	for(int i=1;i<=4;i++){
		tx=x+dx[i];
		ty=y+dy[i];
		if(b[tx][ty]>f+1 && a[tx][ty]!='#'){
			dfs(tx,ty,f+1);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			b[i][j]=INT_MAX;
		}
	}
	dfs(1,1,1);
	cout<<b[n][m];
	return 0;
}



#include<bits/stdc++.h>
using namespace std;
#define N 50
int n,m,cnt=1,sx,sy;
int dx[5]={0,0,-1,0,1};
int dy[5]={0,-1,0,1,0};
struct coord{
	int x;
	int y;
};
bool vis[N][N];
char a[N][N];
int dep[N][N];
queue<coord> Q;
void bfs(int sx,int sy){
	coord tmp={sx,sy};
	Q.push(tmp);
	dep[sx][sy]=1;
	vis[sx][sy]=1;
	while(!Q.empty()){
		coord u=Q.front();
		int x=u.x,y=u.y;
		Q.pop();
		for(int i=1;i<=4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&vis[tx][ty]!=1&&a[tx][ty]=='.'){
				dep[tx][ty]=dep[x][y]+1;
				vis[tx][ty]=1;
				coord tmp={tx,ty};
				Q.push(tmp);
				if(tx==n&&ty==m) return;
			}
		}
	}		
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	bfs(1,1);
	cout<<dep[n][m];
}

来源/分类

提交提交记录统计露一手!