题目描述

难度分:$2600$

输入$n$、$m(1 \leq n,m \leq 1000)$，$k(1 \leq k \leq min(40,nm))$和$n$行$m$列的网格图，元素范围$[1,k]$。

有$k$种颜色，格子的值表示格子的颜色。保证每种颜色至少有一个对应的格子。

然后输入$q(1 \leq q \leq 10^5)$和$q$个询问，每个询问输入起点格子行列编号$(r_1,c_1)$和终点格子行列编号$(r_2,c_2)$。编号从$1$开始。

每次操作，你可以移动到上下左右的相邻格子，或者传送到任意和当前格子颜色相同的格子。

对于每个询问，输出从起点到终点的最小操作次数。

输入样例$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

输出样例$1$

2
0

输入样例$2$

4 4 8
1 2 2 8
1 3 4 7
5 1 7 6
2 3 8 8
4
1 1 2 2
1 1 3 4
1 1 2 4
1 1 4 4

输出样例$2$

2
3
3
4

算法

BFS+枚举

从起点$(r_1,c_1)$到终点$(r_2,c_2)$只有两种方式，一种是直接走，此时步数就是$|r_1-r_2|+|c_1-c_2|$。一种是要经过某种颜色进行传送中转。如果此时我们有一个$dist$数组，$dist[c][x][y]$表示从$(x,y)$位置到颜色$c$的任意格子的最短距离，那就很好处理了，枚举中间那个传送颜色$c \in [1,k]$，$dist[c][r_1][c_1]+dist[c][r_2][c_2]+1$的最小值就是这种方案的答案（即先从$(r_1,c_1)$到一个颜色为$c$的格子，再通过一次传送到一个颜色为$c$的格子，最后从这个格子到$(r_2,r_2)$）。而这两种方式中步数的较小值就是最终答案。

现在问题就在于如何预处理出$dist$数组？我们可以对每种颜色$c \in [1,k]$进行反向的多源BFS，从所有颜色为$c$的格子开始做宽搜，求所有格子距离颜色为$c$的格子的最短路。扩展队列的时候有两种方式，如果出队位置是$(x,y)$，可以直接走$4$个偏移量，正常移动一步；如果$(x,y)$所属颜色还未被访问过，其他与$(x,y)$颜色相同的格子就可以从$(x,y)$出发经过一次传送到达，遍历一遍所有颜色为$a[x][y]$的格子，更新步数即可。这就还需要一个$c2p$数组，$c2p[c]$是所有颜色为$c$的点集数组。

复杂度分析

时间复杂度

做$k$次BFS，每次的时间复杂度为$O(nm)$，因此BFS预处理的时间复杂度为$O(knm)$。而每次询问需要遍历$k$种颜色，因此处理询问的时间复杂度为$O(qk)$。整个算法的时间复杂度为$O(k(nm+q))$。

空间复杂度

距离数组$dist$的空间复杂度为$O(knm)$；标记每种颜色是否被遍历过的$st$数组空间复杂度为$O(k)$；存储每种颜色点集的$c2p$数组需要存$O(nm)$个点，因此空间复杂度为$O(nm)$。整个算法的额外空间复杂度为$O(knm)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 1010, K = 41;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, k, q, a[N][N], dist[K][N][N];
bool st[K];
vector<PII> c2p[K];

void preprocess() {
    for(int c = 1; c <= k; c++) {
        memset(st, 0, sizeof(st));
        queue<PII> que;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(a[i][j] == c) {
                    que.push({i, j});
                    dist[c][i][j] = 0;
                }
            }
        }
        st[c] = true;
        while(!que.empty()) {
            auto pir = que.front();
            que.pop();
            int x = pir.first, y = pir.second;
            if(!st[a[x][y]]) {
                // 走到了一个从未到过的颜色，通过传送就能一步到达任何这个颜色的位置
                st[a[x][y]] = true;
                for(auto&point: c2p[a[x][y]]) {
                    int nx = point.first, ny = point.second;
                    if(dist[c][nx][ny] > dist[c][x][y] + 1) {
                        dist[c][nx][ny] = dist[c][x][y] + 1;
                        que.push({nx, ny});
                    }
                }
            }
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if(1 <= nx && nx <= n && 1 <= ny && ny <= m && dist[c][nx][ny] > dist[c][x][y] + 1) {
                    dist[c][nx][ny] = dist[c][x][y] + 1;
                    que.push({nx, ny});
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; i++) {
        c2p[i].clear();
    }
    memset(dist, 0x3f, sizeof(dist));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            c2p[a[i][j]].push_back({i, j});
        }
    }
    preprocess();
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) {
        int r1, c1, r2, c2;
        scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
        int ans = abs(r1 - r2) + abs(c1 - c2);
        for(int c = 1; c <= k; c++) {
            ans = min(ans, dist[c][r1][c1] + dist[c][r2][c2] + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}