dfs爆TLE解决方案
查看原帖
dfs爆TLE解决方案
1229738
CyansQwQ楼主2024/5/15 21:20

我是蒟蒻(没学几天,还请大佬勿喷),因为这道题不能发题解,所以来这里发表一下我的看法 首先,这道题与P1605其实是同一道,P1605是找有几条路,这道题是判定,先给出TLE的代码,因为n,m 最大100,所以肯定会TLE(2^100)

// Problem: B3625 迷宫寻路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3625
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
char g[N][N];
bool flag=false;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
	if(x==n&&y==m){flag=true;return;}
	g[x][y]='#';
	
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<1||a>n||b<1||b>m)continue;
		if(g[a][b]=='#'){continue;}
		dfs(a,b);
		g[a][b]='.';
	}
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++)cin>>g[i][j];
	dfs(1,1);
	if(flag)cout<<"Yes";
	else cout<<"No";
	return 0;
}
再者,给出另一种思维,大家都做过连通图吧,就是类似P1596这样的题,用DFS判断一个矩阵中有几块连在一起的图形(因为我刚学算法没多久,董晓老师叫它n连通,为了方便记忆,我叫它连通图,貌似这个说法并不准确,因为图论好像有这种东西),我们只用判断与(1,1)连通的图中,是否存在(n,m)就可以了,存在,则两点连通,自然可以到达,反之不能到达,所以用求连通图的板子改一下就好了(或是迷宫板子不进行回溯,一搜到底!!!)
```cpp
// Problem: B3625 迷宫寻路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3625
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans;
char g[N][N];
bool flag=false,ok=false;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
	if(x==n&&y==m){flag=true;return;}
	g[x][y]='#';
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<1||a>n||b<1||b>m)continue;
		if(g[a][b]=='#'){ans++;continue;}
		dfs(a,b);
	}
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++)cin>>g[i][j];
	dfs(1,1);
	if(flag)cout<<"Yes";
	else cout<<"No";
	return 0;
}
2024/5/15 21:20
加载中...