93分求助,悬关!!!
查看原帖
93分求助,悬关!!!
730192
gaomingyang101011楼主2024/3/16 10:35
#include<iostream>
#include<queue>
using namespace std;
const int xx[]={0,0,1,-1};
const int yy[]={1,-1,0,0};
int n,m;
int t[305][305];
char a[305][305];
int qx,qy,zx,zy;
bool vis[305][305];
struct node{
	int x,y;
};
void bfs(int x,int y){
	queue<node> q;
	q.push({x,y});
	vis[x][y]=1;
	while(q.size()){
		int dx=q.front().x,dy=q.front().y;
		if(dx==qx&&dy==qy){
			cout<<t[dx][dy];
			return;
		}
		q.pop();
		for(int i=0;i<4;i++)
			if(dx+xx[i]>0&&dx+xx[i]<=n&&dy+yy[i]>0&&dy+yy[i]<=m&&a[dx+xx[i]][dy+yy[i]]!='#'&&vis[dx+xx[i]][dy+yy[i]]==0){
				if(a[dx+xx[i]][dy+yy[i]]>='A'&&a[dx+xx[i]][dy+yy[i]]<='Z'){;
					t[dx+xx[i]][dy+yy[i]]=t[dx][dy]+1;
					for(int k=1;k<=n;k++)
						for(int j=1;j<=m;j++)
							if(a[k][j]==a[dx+xx[i]][dy+yy[i]]&&(k!=dx+xx[i]||j!=dy+yy[i])){
								q.push({k,j});
								t[k][j]=t[dx+xx[i]][dy+yy[i]];
							}
				}
				else{
					vis[dx+xx[i]][dy+yy[i]]=1;
					t[dx+xx[i]][dy+yy[i]]=t[dx][dy]+1;
					q.push({dx+xx[i],dy+yy[i]});
				}
			}
		/*
		cout<<dx<<" "<<dy<<":"<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<t[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl<<endl;
		*/
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@') qx=i,qy=j;
			else if(a[i][j]=='=') zx=i,zy=j;
		}
	bfs(zx,zy);
	return 0;
}
2024/3/16 10:35
加载中...