CodeForces-1301F Super Jaber

传送门：CodeForces-1301F

思路分析

bfs处理除出每个点到各种颜色的最短距离
$dis[i][x][y]$表示坐标为$(x,y)$的点到$i$颜色的最短距离
那么两个点的最短距离就是两个点到同一个颜色的距离+1的最小值

样例输入

3 4 5
1 2 1 3    
4 4 5 5
1 2 1 3
2
1 1 3 4
2 2 2 2

样例输出

2
0

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1010;

int n,m,k;
vector<pair<int,int>>col[41];
int a[N][N],dis[41][N][N];
int vis[N][N],viscol[41];
int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};

void bfs(int x) {
    mem(vis,0);
    mem(viscol,0);
    viscol[x]=1;
    queue<pair<int,int>>q;
    for(auto i:col[x]) {
        q.push(i);
        dis[x][i.fi][i.se]=0;
        vis[i.fi][i.se]=1;
    }
    while(!q.empty()) {
        int nowx=q.front().fi;
        int nowy=q.front().se;
        q.pop();
        if(!viscol[a[nowx][nowy]]) {
            for(auto i:col[a[nowx][nowy]]) {
                int nx=i.fi;
                int ny=i.se;
                if(!vis[nx][ny]) {
                    dis[x][nx][ny]=dis[x][nowx][nowy]+1;
                    vis[nx][ny]=1;
                    q.push(mp(nx,ny));
                }
            }
        }
        viscol[a[nowx][nowy]]=1;
        for(int i=0; i<4; i++) {
            int nx=nowx+dx[i];
            int ny=nowy+dy[i];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(!vis[nx][ny]) {
                dis[x][nx][ny]=dis[x][nowx][nowy]+1;
                vis[nx][ny]=1;
                q.push(mp(nx,ny));
            }
        }
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m>>k;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin>>a[i][j];
            col[a[i][j]].push_back(mp(i,j));
        }
    }
    for(int i=1; i<=k; i++)
        bfs(i);
    int q;
    cin>>q;
    while(q--) {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        x1--,x2--,y1--,y2--;
        int ans=abs(x1-x2)+abs(y1-y2);
        for(int i=1; i<=k; i++)
            ans=min(ans,dis[i][x1][y1]+dis[i][x2][y2]+1);
        cout<<ans<<endl;
    }



    return 0;
}