0 pts help
查看原帖
0 pts help
270854
二叉苹果树楼主2021/10/19 23:25
#include<bits/stdc++.h>
using namespace std;
struct crood{
	int x,y;
};
struct capital{
	int x[3],y[3],count=0;
};
queue<crood>Q;
map<char,capital>S;
int walk[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char Map[305][305];
int m,n,vis[305][305],ans[305][305],fnx,fny;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	    {
	        cin>>Map[i][j];
	        if(Map[i][j]>='A'&&Map[i][j]<='Z')
	        {
	        	S[Map[i][j]].x[++S[Map[i][j]].count]=i;
	        	S[Map[i][j]].y[S[Map[i][j]].count]=j;
			}
			else if(Map[i][j]=='@')
			    Q.push((crood){i,j});
			else if(Map[i][j]=='=')
			    fnx=i,fny=j;
	    }
	while(!Q.empty())
	{
		crood u=Q.front();
		int ux=u.x,uy=u.y;
		Q.pop();
		for(int k=0;k<=3;k++)
		{
			int x=ux+walk[k][0],y=uy+walk[k][1];
			if(vis[x][y]==0)
			{
				if(Map[x][y]=='.')
				{
					ans[x][y]=ans[ux][uy]+1;
					Q.push((crood){x,y});
				}
				if(Map[x][y]>='A'&&Map[x][y]<='Z')
				{
					if(x==S[Map[x][y]].x[1]&&y==S[Map[x][y]].y[1])
					    x=S[Map[x][y]].x[2],y=S[Map[x][y]].y[2];
					else
					    x=S[Map[x][y]].x[1],y=S[Map[x][y]].y[1];
					ans[x][y]=ans[ux][uy]+1;
					Q.push((crood){x,y});
				}
			}
		}
	}
	cout<<ans[fnx][fny]<<endl;
	return 0;
}

rt,不会广搜qwq

2021/10/19 23:25
加载中...