蒟蒻一半红一半绿的。。求大佬帮助qwq
查看原帖
蒟蒻一半红一半绿的。。求大佬帮助qwq
480486
倚窗听雨落楼主2021/4/25 21:56
#include <bits/stdc++.h>
using namespace std;
struct point{
    int x;
    int y;
    int step;
    point(int xx,int yy,int stepp):x(xx),y(yy),step(stepp){}
};
bool ifgo[28];
int match[28][2][2];
bool vis[305][305];
int special[305][305];
int xxx[]={0,1,-1,0,0},yyy[]={0,0,0,1,-1};
int sx,sy,fx,fy;
int main()
{
    int ans;
    queue<point> q;
    char now;
    memset(ifgo,0,sizeof(ifgo));
    memset(match,0,sizeof(match));
    memset(special,0,sizeof(special));
    memset(vis,0,sizeof(vis));
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>now;
            if(now=='@') {sx=i;sy=j;}
            else if(now=='=') {fx=i;fy=j;}
            else if(now=='#') vis[i][j]=1;
            else if(now>='A'&&now<='Z') 
            {
                special[i][j]=now-'A'+1;
                if(ifgo[now-'A'+1])
                {
                    match[now-'A'+1][1][0]=i;
                    match[now-'A'+1][1][1]=j;
                }
                else
                {
                    special[i][j]=now-'A'+1;
                    ifgo[now-'A'+1]=1;
                    match[now-'A'+1][0][0]=i;
                    match[now-'A'+1][0][1]=j;
                }
            }
        }
    }
    q.push(point(sx,sy,0));
    vis[sx][sy]=1;
    while(!q.empty())
    {
        //cout
        point pnow=q.front();q.pop();
        if(pnow.x==fx&&pnow.y==fy) 
        {
            ans=pnow.step;
            break;
        }
        //cout<<"fuck"<<endl;
        for(int i=1;i<=4;i++)
        {
            if(pnow.x+xxx[i]>0&&pnow.x+xxx[i]<=n&&pnow.y+yyy[i]>0&&pnow.y+yyy[i]<=m&&(!vis[pnow.x+xxx[i]][pnow.y+yyy[i]]))
            {
                if(!special[pnow.x+xxx[i]][pnow.y+yyy[i]]) {q.push(point(pnow.x+xxx[i],pnow.y+yyy[i],pnow.step+1));vis[pnow.x+xxx[i]][pnow.y+yyy[i]]=1;}
                else
                {
                    vis[pnow.x+xxx[i]][pnow.y+yyy[i]]=1;
                    int xxnow=pnow.x+xxx[i],yynow=pnow.y+yyy[i];
                    if(match[special[xxnow][yynow]][0][0]==xxnow&&match[special[xxnow][yynow]][0][1]==yynow)
                    {
                        vis[match[special[xxnow][yynow]][1][0]][match[special[xxnow][yynow]][1][1]]=1;
                        q.push(point(match[special[xxnow][yynow]][1][0],match[special[xxnow][yynow]][1][1],pnow.step+1));
                    }
                    else
                    {
                        vis[match[special[xxnow][yynow]][0][0]][match[special[xxnow][yynow]][0][1]]=1;
                        q.push(point(match[special[xxnow][yynow]][0][0],match[special[xxnow][yynow]][0][1],pnow.step+1));
                    }
                }
            }
        }
        //cout<<"fu";
    }
    cout<<ans<<endl;
    return 0;
}
2021/4/25 21:56
加载中...