86分dfs,两个超时样例wa6和wa8求佬佬调!
查看原帖
86分dfs,两个超时样例wa6和wa8求佬佬调!
1263218
Lntano_LYC楼主2024/11/3 13:11
#include <bits/stdc++.h>
using namespace std;
int n,m,ans = 0x3f3f3f3f,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},st[305][305],dis[305][305];
char w[305][305],c;
using pii = pair<int,int>;
pii sr,ed,o;
map<char,pair<pii,pii>> mp;//两个坐标比对 
void dfs(int x,int y,int t) 
{
	if(w[x][y]=='=') {ans=min(t,ans);return;}
	if(w[x][y]>='A'&&w[x][y]<='Z') {
		int nx=x,ny=y;char cc = w[nx][ny];//变项与不变项 
		if((nx==mp[cc].first.first)&&(ny==mp[cc].first.second)) 
			x=mp[cc].second.first,y=mp[cc].second.second;
		else x=mp[cc].first.first,y=mp[cc].first.second;
	}
	for(int i = 0 ; i <= 3 ; i++) {
		int xx = x+dx[i],yy=y+dy[i];
		if(dis[xx][yy]<=t+1) continue;
		dis[xx][yy]=t+1;
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&w[xx][yy]!='#'&&!st[xx][yy]){ 
			st[xx][yy]=true;
			dfs(xx,yy,t+1);
			st[xx][yy]=false;
		}
	}
	return; 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);	 
	cin >> n >> m;
	o={0,0}; 
	memset(dis,0x3f,sizeof dis);
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 1 ; j <= m ; j++) {
			cin >> w[i][j];
			if(w[i][j]=='@') sr={i,j};
			else if((w[i][j]>='A')&&(w[i][j]<='Z')) 
				if(mp[w[i][j]].first==o) mp[w[i][j]].first={i,j};
				else mp[w[i][j]].second = {i,j};
		}
	}
	st[sr.first][sr.second]=1;
	dis[sr.first][sr.second]=0;//到这个点所需要的时间 
	dfs(sr.first,sr.second,0);
	cout << ans << endl;
	return 0;
}
2024/11/3 13:11
加载中...