大佬看看我错哪里了
查看原帖
大佬看看我错哪里了
1449144
Enchantment楼主2025/2/4 16:14
#include <bits/stdc++.h>
#define endl "\n"
#define N 505
using i64 = long long;
using namespace std;
#define  PII  pair<int,int> 
#define  PSI  pair<string,int>

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int vis[N][N];
int n,m;
char ch[N][N];
unordered_map<char ,vector<PII>>pp;

void bfs(int x,int y){
	queue<PII>q;
	vis[x][y]=1;
	q.push({x,y});
	queue<int>cnt;
	cnt.push(0);
	while(!q.empty()){
		auto cu=q.front();
		q.pop();
	    int cx=cu.first;
		int cy=cu.second;
		int tim=cnt.front();
		cnt.pop();
		if(ch[cx][cy]=='='){
			cout<<tim<<endl;
			return ;
		}
		for(int i=0;i<4;i++){
			int nx=cx+dx[i];
			int ny=cy+dy[i];
		    int nextim=tim+1;
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0){
				if(ch[nx][ny]=='.'||ch[nx][ny]=='='){
					vis[nx][ny]=1;
					q.push({nx,ny});
					cnt.push(nextim);
				}else if(ch[nx][ny]>='A'&&ch[nx][ny]<='Z'){
					char tron=ch[nx][ny];
					vis[nx][ny]=1;
					for(auto it:pp[tron]){
						if(it.first!=nx||it.second!=ny){
							if(vis[it.first][it.second]==0){
								vis[it.first][it.second]=1;
								q.push({it.first,it.second});
								cnt.push(nextim);
							}
						}
					}
				}
			}
		}
	}
}

void solve(){
    cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch[i][j];
			if(ch[i][j]>='A'&&ch[i][j]<='Z'){
				pp[ch[i][j]].push_back({i,j});
			}
		}
	}
	
	int index1;
	int index2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='@'){
				index1=i;
				index2=j;
				break;
			}
		}
	}
	bfs(index1,index2);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	solve();
	return 0;
}

2025/2/4 16:14
加载中...