蒟蒻广搜GG了
查看原帖
蒟蒻广搜GG了
195349
未泯楼主2021/10/6 16:22
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[310][310];
int vis[310][310]= {0},ans[310][310];
int cx[5]= {0,1,-1,0,0},cy[5]= {0,0,0,1,-1};
struct point {
	int x,y;
};
point find(int x,int y) {
	int q=s[x][y];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			point a;
			a.x=i,a.y=j;
			if(s[i][j]==q && i!=x) {
				return a;
			}
		}
	}
}
void bfs(int x,int y) {
	ans[x][y]=0,vis[x][y]=1;
	queue<point>Q;
	Q.push({x,y});
	while(!Q.empty()) {
		point w=Q.front();
		Q.pop();
		int ax=w.x,ay=w.y;
		for(int i=1; i<=4; i++) {
			int bx=ax+cx[i],by=ay+cy[i];
			if(s[bx][by]=='=') {
				printf("%d",ans[ax][ay]+1);
				return ;
			}
			if(vis[bx][by])continue;
			vis[bx][by]=1;
			if(s[bx][by]>='A' && s[bx][by]<='Z') {
				point tp=find(bx,by);
				if(ans[bx][by]>=ans[ax][ay]+1) {
					ans[bx][by]=ans[ax][ay]+1;
					ans[tp.x][tp.y]=ans[bx][by];
					vis[tp.x][tp.y]=1;
				}
				Q.push({tp.x,tp.y});
			} else {
				if(ans[bx][by]>=ans[ax][ay]+1) {
					ans[bx][by]=ans[ax][ay]+1;
				}
				Q.push({bx,by});
			}
		}
	}
}
int main() {
	int sx,sy;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++)ans[i][j]=2147483647;
	}
	for(int i=1; i<=n; i++) {
		string q;
		std::cin>>q;
		for(int j=1; j<=m; j++) {
			s[i][j]=q[j-1];
			if(s[i][j]=='@')sx=i,sy=j;
			if(s[i][j]=='#')vis[i][j]=1;
		}
	}
	bfs(sx,sy);
}
2021/10/6 16:22
加载中...