Codeforces 1301 F. Super Jaber —— bfs，思維

This way

題意：

現在有一張n*m的矩形圖，每個格子有一個顔色，并且每個格子都可以花一秒的時間往周圍四格擴散或者跳到另一個相同顔色的位置。每次問你從(x1,y1)跳到(x2,y2)至少要花多少時間

題解：

首先如果直接走是最短的那麼就直接走，否則就一定至少會在一個顔色進行跳轉。

dis[c][i][j]表示從顔色c跳到位置(i,j)的最少時間

那麼直接進行bfs，首先如果這個顔色沒跳過，就進行跳轉，否則就往旁邊進行擴散即可。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=1e3+5,M=45;
int dis[M][N][N],mp[N][N],n,m,q,k;
queue<pa>Q;
int xmov[]={1,0,-1,0};
int ymov[]={0,1,0,-1};
int cal[M];
void bfs(int c){
    memset(cal,0,sizeof(cal));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]==c)
                Q.push({i,j});
    while(!Q.empty()){
        int x=Q.front().first,y=Q.front().second;Q.pop();
        if(!cal[mp[x][y]]&&mp[x][y]!=c){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    if(i==x&&j==y)continue;
                    if(mp[i][j]==mp[x][y]&&!dis[c][i][j])
                        dis[c][i][j]=dis[c][x][y]+1,Q.push({i,j});
                }
            }
            cal[mp[x][y]]=1;
        }
        for(int i=0;i<4;i++){
            int nx=x+xmov[i],ny=y+ymov[i];
            if(nx<1||nx>n||ny<1||ny>m||dis[c][nx][ny]||mp[nx][ny]==c)continue;
            dis[c][nx][ny]=dis[c][x][y]+1;
            Q.push({nx,ny});
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]);
    for(int i=1;i<=k;i++)
        bfs(i);
    scanf("%d",&q);
    while(q--){
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int ans=abs(x1-x2)+abs(y1-y2);
        //if(mp[x1][y1]==mp[x2][y2])ans=1;
        if(x1==x2&&y1==y2)ans=0;
        for(int i=1;i<=k;i++)
            ans=min(ans,dis[i][x1][y1]+dis[i][x2][y2]+1);
        printf("%d\n",ans);
    }
    return 0;
}