dfs,TLE59分,求优化(虽然是道bfs题)
查看原帖
dfs,TLE59分,求优化(虽然是道bfs题)
750689
CNzzc楼主2024/8/5 21:01
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=3e2+10;
int n,m;
char a[N][N];
bool f[N][N];
struct node{
	int xd,yd,xe,ye;
};
node jl['Z'+10];
int qx,qy,zx,zy;
const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
int ans=INT_MAX;
bool check(int u,int v)
{
	if(u<1 || v<1 || u>n || v>m){
		return false;
	}
	else{
		return true;
	}
}
void dfs(int x,int y,int ct)
{
	if(ct>=ans){
		return;
	}
	//cout<<x<<' '<<y<<endl;
	if(x==zx && y==zy){
		ans=min(ans,ct);
		return;
	}
	int xx,yy;
	up(i,0,3,1){
		xx=x+dx[i];
		yy=y+dy[i];
		if(a[xx][yy]=='#' || !check(xx,yy)){
			continue;
		}
		if(a[xx][yy]>='A' && a[xx][yy]<='Z' && f[xx][yy]==false){
			f[xx][yy]=true;
			if(xx==jl[(int)a[xx][yy]].xd && yy==jl[(int)a[xx][yy]].yd){
				dfs(jl[(int)a[xx][yy]].xe,jl[(int)a[xx][yy]].ye,ct+1);
			}
			else{
				dfs(jl[(int)a[xx][yy]].xd,jl[(int)a[xx][yy]].yd,ct+1);
			}
			f[xx][yy]=false;
		}
		else{
			if(f[xx][yy]==false){
				f[xx][yy]=true;
				dfs(xx,yy,ct+1);
				f[xx][yy]=false;
			}
		}
	}
	return;
}
void solve()
{
	cin>>n>>m;
	up(i,1,n,1){
		up(j,1,m,1){
			cin>>a[i][j];
			if(a[i][j]>='A' && a[i][j]<='Z'){
				if(jl[(int)a[i][j]].xd==0 && jl[(int)a[i][j]].yd==0){
					jl[(int)a[i][j]].xd=i;
					jl[(int)a[i][j]].yd=j;
				}
				else{
					jl[(int)a[i][j]].xe=i;
					jl[(int)a[i][j]].ye=j;					
				}
			}
			if(a[i][j]=='@'){
				qx=i;
				qy=j;
			}
			if(a[i][j]=='='){
				zx=i;
				zy=j;
			}
		}
	}
	f[qx][qy]=true;
	dfs(qx,qy,0);
	cout<<ans;
	return;
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int _=1;
	//cin>>_;
	while(_--){
		solve();
	}
	return 0;
}
2024/8/5 21:01
加载中...