76分求助!!!
查看原帖
76分求助!!!
680318
Wd518518楼主2023/9/21 20:49
#include<bits/stdc++.h>
using namespace std;
int n,m,ia,ja,jb,ib,dis[310][310],vis[310][310],dx,dy,xx,yy;
string aa[310];
char a[310][310];
void find(int wx,int wy)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
           if(a[wx][wy]==a[i][j]&&(wx!=i||wy!=j)){
           	   xx=i;
           	   yy=j;
//           	   cout<<i<<"  "<<j<<endl;
           	   break;
           }
}
int bfs(int ii,int jj)
{
	int x[5]={0,1,-1,0,0},y[5]={0,0,0,1,-1};
	queue<pair<int,int> >q;
	q.push(make_pair(ii,jj));
	vis[ii][jj]=1;
	
	while(!q.empty()){
		xx=q.front().first;
		yy=q.front().second;
		q.pop();
		if(ib==xx&&jb==yy)return dis[xx][yy];
		
		if(a[xx][yy]>='A'&&a[xx][yy]<='Z'){
			int x1=xx,y1=yy;
			find(xx,yy);
			dis[xx][yy]=dis[x1][y1];
//			vis[xx][yy]=1;
		}
		
		for(int i=1;i<=4;i++){
			dx=xx+x[i];
			dy=yy+y[i];
			if(dx<1||dx>n||dy<1||dy>m||a[dx][dy]=='#'||vis[dx][dy]==1)continue;
				vis[dx][dy]=1;
				dis[dx][dy]=dis[xx][yy]+1;
				q.push(make_pair(dx,dy));
			
		}
		
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)cout<<dis[i][j]<<" ";
//		cout<<endl;
//		
//	}
	return -1;
	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>aa[i];
		for(int j=0;j<m;j++){
			a[i][j+1]=aa[i][j];
			if(a[i][j]=='@'){
				ia=i;
				ja=j;
			}
			if(a[i][j]=='='){
				ib=i;
				jb=j;
			}
		}
	}
	cout<<bfs(ia,ja);	
}
2023/9/21 20:49
加载中...