52分蒟蒻求助
查看原帖
52分蒟蒻求助
381566
_lzh_楼主2021/3/22 13:25

Rt

#include<bits/stdc++.h>
#define int long long
#define N 1010
using namespace std;
struct fk
{
    int x,y,ans;
};
queue<fk> q;
int n,m,dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}},pd[N][N],pddd[N][N];
string s[N];
void change(int &x,int &y)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]==s[x][y]&&x!=i&&y!=j)
            {
                x=i,y=j;
                return;
            }
        }
    }
}
fk cha(int x,int y)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]==s[x][y]&&x!=i&&y!=j)
            {
                return (fk){i,j,0};
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='@')q.push((fk){i,j,0});
    while(!q.empty())
    {
        fk a=q.front();
        q.pop();
        int x=a.x,y=a.y,ans=a.ans;
        if(s[x][y]=='=')
        {
            cout<<ans+1;
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0],ny=y+dir[i][1];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]!='#'&&pd[nx][ny]==0)
            {
                pd[nx][ny]=1;
                if(s[nx][ny]=='=')
                {
                    cout<<ans+1;
                    return 0;
                }
                else if(s[nx][ny]=='.')q.push((fk){nx,ny,ans+1});
                else
                {
                	if(pddd[nx][ny]==1)
                	{
                		fk aa=cha(nx,ny);
                		if(pddd[aa.x][aa.y]==1)
                		{
                			pddd[nx][ny]++;
                    		change(nx,ny);
                    		pddd[nx][ny]++;
                    		q.push((fk){nx,ny,ans+1});
						}
                		else q.push((fk){nx,ny,ans+1});
					}
					else
					{
                		pddd[nx][ny]++;
                    	change(nx,ny);
                    	pddd[nx][ny]++;
                    	q.push((fk){nx,ny,ans+1});
                    }
                }
            }
        }
    }
    return 0;
}
2021/3/22 13:25
加载中...