40分求助
查看原帖
40分求助
1133203
Ssssshuai楼主2024/3/16 13:49
#include <iostream>	
#include <string>

using namespace std;

int n,m;
//迷宫 
char maze[110][110]; 
//标记
bool vis[110][110];
//移动操作
int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};

bool in(int x, int y)
{
	return 0<=x && x<n && 0<=y && y<m;
}

bool dfs(int x, int y)
{
	//结束条件 
	if (x==n && y==m)
	{
		return true;
	}
	
	//标记
	vis[x][y] = true;
	
	//移动
	for (int i=0; i<4; i++) 
	{
		int tx = x + dir[i][0];//当i等于0时,执行上移操作,
		int ty = y + dir[i][1];//接下来按逆时针移动
		
		//如果在范围内,并且不是墙壁,没有被标记过,就继续深度搜索 
		if (in(tx, ty) && maze[tx][ty] != '#' && !vis[tx][ty])
		{
			if (dfs(tx, ty))
			{
				return true;
			}
		} 
	}
	
	return false; 
}

int main()
{
	//输入迷宫地图
	cin >> n >> m;
	for (int i=1; i<=n; i++)	
	{
		for (int j=1; j<=m; j++)
		{
			cin >> maze[i][j];
		}
	}
	
	//DFS 
	if (dfs(1, 1))
	{
		cout << "Yes"; 
	}
	else 
	{
		cout << "No";
	}
	
	return 0;
}
2024/3/16 13:49
加载中...