94分wa8求助
查看原帖
94分wa8求助
666130
slime_fan楼主2023/7/30 23:45
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=310;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char a[N][N];
string s;
int n,m;
vector<PII> temp;
map<char,vector<PII>> mp;
map<PII,PII> p;
int stx,sty,edx,edy;
bool st[N][N];
int dist[N][N],cnt[N][N];
int ans[N];
bool ok=false;
void bfs(int xx,int yy){
	queue<PII> q;
	st[xx][yy]=true;
	dist[xx][yy]=0;
	q.push({xx,yy});
	while(q.size()){
		PII t=q.front();
		q.pop();
		if(t.x==edx && t.y==edy){
			cout<<dist[t.x][t.y];
			return;
		}
		PII temp;
		temp.x=t.x;
		temp.y=t.y;
		if(p.count(temp)){
			dist[p[t].x][p[t].y]=dist[t.x][t.y];
			temp.x=p[t].x;
			temp.y=p[t].y;
			st[t.x][t.y]=true;
		}
		for(int i=0;i<4;i++){
			int nex=temp.x+dx[i],ney=temp.y+dy[i];
			if(nex<1 || nex>n || ney<1 || ney>m || st[nex][ney]) continue;
			if(a[nex][ney]=='#') continue;
			dist[nex][ney]=dist[temp.x][temp.y]+1;
			q.push({nex,ney});
			st[nex][ney]=true;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	memset(dist,0x3f,sizeof dist);
	memset(st,false,sizeof st);
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=1;j<=m;j++){
			a[i][j]=s[j-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]>='A' && a[i][j]<='Z'){
				mp[a[i][j]].push_back({i,j});
			}
			if(a[i][j]=='@'){
				stx=i;sty=j;
			}
			if(a[i][j]=='='){
				edx=i;edy=j;
			}
		}
	}
	for(auto it:mp){
		temp=it.y;
		p[temp[0]]=temp[1];
		p[temp[1]]=temp[0];
	}
	bfs(stx,sty);
	return 0;
} 
2023/7/30 23:45
加载中...