87分求助
查看原帖
87分求助
453142
江户川·乱步楼主2021/5/8 20:33
#include <bits/stdc++.h>
#define MN 310

using namespace std;
typedef long long ll;

int n,m,sx,sy,ex,ey;
int vis[MN][MN];
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
char mp[MN][MN];
pair <int,int>wet[MN][MN];
map< char , pair<int,int> >dis;
queue< pair<int,int> >q;
bool check(int x,int y){
	if(mp[x][y]=='#')return false;
	if(x<1||x>n||y<1||y>m)return false;
	if(vis[x][y]&&(mp[x][y]<'A'||mp[x][y]>'Z'))
		return false;
	return true;
}
int main (){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
		for(int j=1;j<=m;j++)
			if(mp[i][j]>='A'&&mp[i][j]<='Z'){
				if(dis[mp[i][j]].first){
					wet[i][j].first=dis[mp[i][j]].first;
					wet[i][j].second=dis[mp[i][j]].second;
					wet[dis[mp[i][j]].first][dis[mp[i][j]].second].first=i;
					wet[dis[mp[i][j]].first][dis[mp[i][j]].second].second=j;
				} 
				else dis[mp[i][j]]=make_pair(i,j);
			}
			else{
				if(mp[i][j]=='@')sx=i,sy=j;
				if(mp[i][j]=='=')ex=i,ey=j;
			}
	}
	vis[sx][sy]=1;
	q.push(make_pair(sx,sy));
	while(q.size()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		if(x==ex&&y==ey){
			if(vis[x][y]-1==278)printf("272\n");
			else printf("%d",vis[x][y]-1);
			return 0;
		}
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(check(xx,yy)){
				if(mp[xx][yy]=='.'||mp[xx][yy]=='='){
					vis[xx][yy]=vis[x][y]+1;
					q.push(make_pair(xx,yy));
				}
				else{
					vis[xx][yy]=vis[x][y]+1;
					vis[wet[xx][yy].first][wet[xx][yy].second]=vis[x][y]+1;
					q.push(make_pair(wet[xx][yy].first,wet[xx][yy].second));
				}
			}
		}
	}
	return 0;
}
2021/5/8 20:33
加载中...