dfs 求调 TLE
查看原帖
dfs 求调 TLE
964148
cqbzrjx楼主2024/3/16 09:53
//洛谷 B3625 迷宫寻路 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};//四个方向
int n,m;
int sx,sy,ex,ey;//sx和sy指起点坐标,ex和ey指终点坐标
int vis[105][105];//当前点搜过的情况
char mp[105][105];//地图
int res;//存储最终值
inline bool check(int x,int y)
{
	if(mp[x][y] == '#') return false;//遇到有怪兽的方格的情况
	if(x < 0 || x >= n || y < 0 || y >= m) return false;//超出边界的情况
	if(vis[x][y]) return false;//当前以搜过的情况
	return true;
}
inline void dfs(int x,int y,int step)//step为步数
{
	vis[x][y] = 1;
	if(x == ex && y == ey)//找到终点
	{
		res = min(res,step);//存储值
		return;
	}
	for(int i = 0;i < 4;i++)//四个方向方向
	{
		int fx = x + dx[i];//进行搜索的x坐标
		int fy = y + dy[i];//进行搜索的y坐标
		if(check(fx,fy))//判断是否可行
		{
			dfs(fx, fy,step + 1);
			vis[fx][fy] = 0;
		}
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	res = 1e5;
	memset(vis,0,sizeof vis);
	for(int i = 0;i < n;i++)
	{
		cin>>mp[i];
	}
	sx = 0,sy = 0,ex = n - 1,ey = m - 1;
	dfs(sx,sy,0);//搜索
	if(res == 1e5) cout<<"No";
	else cout<<"Yes";
	return 0;
}
2024/3/16 09:53
加载中...