1 条题解

  • 0
    @ 2025-10-8 16:53:51
    #include<bits/stdc++.h>
    using namespace std;
    const int N=510;
    int n,m,X1,Y1,X2,Y2,d[N][N];
    char ss[N][N];
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    struct node{int x,y;};
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0 && m==0)break;
            for(int i=1;i<=n;i++)scanf("%s",ss[i]+1);
            scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
            X1++;Y1++;X2++;Y2++;
    
            memset(d,63,sizeof(d));d[X1][Y1]=0;
            queue<node>Q;Q.push({X1,Y1});
            while(Q.size())
            {
                int x=Q.front().x,y=Q.front().y;Q.pop();
                for(int i=0;i<=3;i++)
                {
                    int tx=x+dx[i],ty=y+dy[i];
                    if(tx<=n && tx>=1 && ty<=m && ty>=1)
                    {
                        if(ss[x][y]!=ss[tx][ty])
                        {
                            if(d[x][y]+1<d[tx][ty])
                            {
                                d[tx][ty]=d[x][y]+1;
                                Q.push({tx,ty});
                            }
                        }
                        else
                        {
                            if(d[x][y]<d[tx][ty])
                            {
                                d[tx][ty]=d[x][y];
                                Q.push({tx,ty});
                            }
                        }
                    }
                }
            }
            printf("%d\n",d[X2][Y2]);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    760
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    60
    已通过
    18
    上传者