站外题求助（DFS）

题目：

题目描述

有一张迷宫地图，其有 R R 行 C C 列，共 R × C R×C 个格子。每个格子中为字符 '.' 或字符'#' ，分别表示平地、墙。

已知迷宫入口为左上角格子，出口为右下角格子。

请问，从入口走到出口，至少需要走几个格子（包括入口格子、出口格子）？若无法走到出口，请输出 − 1 −1 。

注：每一步只能移动到相邻4个方向（上、下、左、右）的格子上。

输入格式

输入共 1 + R 1+R 行。

第1行包含两个整数，即题目中所述的 R , C R,C 。

接下来的 R R ，为这张迷宫地图。即每行包含 C C 个字符，这些字符只可能是字符 '.' 或字符'#' 。

输出格式

输出包含一个整数，即至少需要走几个格子。（注：若无法走到出口，则输出 − 1 −1 ）

输入输出样例输入 #1

CPP

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

输出 #1

CPP

输入 #2

CPP

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

输出 #2复制

CPP

-1

说明/提示

测试数据说明：对于前50%的测试数据， 1 ≤ R , C ≤ 5 1≤R,C≤5 对于后50%的测试数据， 5 ＜ R , C ≤ 100 5＜R,C≤100

代码：

CPP

#include <iostream>
using namespace std;
int r,c,mincnt=114514;
char g[101][101]={'.'};
bool vis[101][101]={false},can=false;
int amns[101][101]={0};
int f[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int dx,int dy,int cnt){
	if(dx==r && dy==c){
		return;
	} 
	vis[dx][dy]=true;
	
	
	for(int i=0;i<4;i++){
		int fx=f[i][0]+dx;
		int fy=f[i][1]+dy;
		if(fx>=1 && fx<=r && fy>=1 && fy<=c){
			if(!vis[fx][fy] && g[fx][fy]=='.' && amns[dx][dy]+1<amns[fx][fy]){
				amns[fx][fy]=amns[dx][dy]+1;
				dfs(fx,fy,cnt+1);
			}                               
		}
			
	}
	vis[dx][dy]=false;
	
	
	
} 
int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>g[i][j]; 
		}
	} 
	dfs(1,1,0);
	if(amns[r][c]!=0)cout<<amns[r][c];
	else cout<<"-1";
	return 0;
}

求助！

站外题求助（DFS）

讨论操作

回复

相关推荐

站外题求助（DFS）