Discussion Detail - 追梦算法网

问答
为什么我的DFS会超时呢（求学长学姐指明一下，谢谢）(已解决)
Lucia-X LV 8 @ 2023-7-2 11:39:59

题目是 #E429. 【基础】走出迷宫的最少步数第四个样例TEL QAQ（bfs能做）

#include <bits/stdc++.h>
using namespace std;
int n,m,step;
char mp[50][50];
int vis[50][50];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y,int nstep){
	if(x==n&&y==m){
		step=min(step,nstep);
		return ;
	}
	vis[x][y]=1;
	
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>0&&ny>0&&nx<=n&&ny<=m&&!vis[nx][ny]&&mp[nx][ny]=='.'){
			dfs(nx,ny,nstep+1);
		}
	}
		vis[x][y]=0;
}
int main(){
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	step=n*m+1;
	dfs(1,1,1);
	cout<<step;
	return 0;
}

ZXL Acmer LV 10 MOD @ 2023-7-13 23:28:03

dfs+记忆化搜索

#include <bits/stdc++.h>
using namespace std;
int n,m,step;
char mp[50][50];
int dist[50][50];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y,int nstep){
	if(dist[x][y]>nstep) dist[x][y]=nstep;
	else return;
	if(x==n&&y==m){
		step=min(step,nstep);
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>0&&ny>0&&nx<=n&&ny<=m&&mp[nx][ny]=='.'){
			dfs(nx,ny,nstep+1);
		}
	}
}
int main(){
	cin>>n>>m;
	memset(dist,0x3f,sizeof(dist));
	for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	step=n*m+1;
	dfs(1,1,1);
	cout<<step;
	return 0;
}

ZXL Acmer LV 10 MOD @ 2023-7-13 23:12:16
Edited

建议bfs,直接写dfs解决这类问题时间复杂度高得多，但dfs如果采用记忆化搜索应该也能过