40分蒟蒻求助!
查看原帖
40分蒟蒻求助!
401052
Endline楼主2021/4/18 09:11
#include<bits/stdc++.h>
using namespace std;

int n,m,sx,sy,fx,fy;
int dx[4]={0,1,-1,0},dy[4]={-1,0,0,1};
char a[310][310];
bool f[310][310];

struct node{
	int x,y,step;
};

node find(int x,int y,char z)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==z&&i!=x&&j!=y)return node{i,j,0};
}

queue<node>q;

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]=='@')sx=i,sy=j,f[i][j]=true;
			if(a[i][j]=='=')fx=i,fy=j;
		}
	q.push((node){sx,sy,0});
	while(!q.empty())
	{
		node t=q.front();
		if(t.x==fx&&t.y==fy)
		{
			cout<<t.step;
			return 0;
		}
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(a[nx][ny]=='#')continue;
			if(f[nx][ny])continue;
			if(a[nx][ny]>='A'&&a[nx][ny]<='Z')
			{
				node del=find(nx,ny,a[nx][ny]);
				f[nx][ny]=1;
				nx=del.x,ny=del.y;
				if(f[nx][ny])continue;
				f[nx][ny]=1;
				q.push((node){nx,ny,t.step+1});
			}
			f[nx][ny]=1;
			q.push((node){nx,ny,t.step+1});
		}
	}
	return 0;
}

qwq

2021/4/18 09:11
加载中...