DFS代码50分5个TLE
查看原帖
DFS代码50分5个TLE
528612
Entity_303_楼主2023/6/3 10:21

求大佬帮忙改改

#include<bits/stdc++.h>
using namespace std;
int n,m;
char ch[110][100];
bool vis[110][110];
bool dfs(int x,int y)//深搜
{
	if(x==n && y==m)
	{
		return 1;
	}
	else
	{
		if(x+1<=n && ch[x+1][y]!='#' && !vis[x+1][y])
		{
			vis[x+1][y]=1;
			if(dfs(x+1,y))
			{
				return 1;
			}
			vis[x+1][y]=0;
		}
		if(x-1>=1 && ch[x-1][y]!='#' && !vis[x-1][y])
		{
			vis[x-1][y]=1;
			if(dfs(x-1,y))
			{
				return 1;
			}
			vis[x-1][y]=0;
		}
		if(y+1<=m && ch[x][y+1]!='#' && !vis[x][y+1])
		{
			vis[x][y+1]=1;
			if(dfs(x,y+1))
			{
				return 1;
			}
			vis[x][y+1]=0;
		}
		if(y-1>=1 && ch[x][y-1]!='#' && !vis[x][y-1])
		{
			vis[x][y-1]=1;
			if(dfs(x,y-1))
			{
				return 1;
			}
			vis[x][y-1]=0;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);//优化
	cin.tie(NULL);//优化
	cout.tie(NULL);//优化
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>ch[i][j];
		}
	}
	bool flag=dfs(1,1);
	if(flag)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
    return 0;
}

评测记录

2023/6/3 10:21
加载中...