Codeforces Round #619 (Div. 2) F. Super Jaber BFS最短路-蒲公英云

Codeforces Round #619 (Div. 2) F. Super Jaber BFS最短路

题目链接：http://codeforces.com/contest/1301/problem/F
题意：n*m的矩阵，每个点都有颜色，每次你可以去相邻的4个点或者任意颜色和当前点相同的点，问最少多少次从A到B
思路：f[k][i][j]表示(i, j)这点到k颜色的点的最短路径，那么最小花费就是min(f[k][r1][c1] + f[k][r2][c2] + 1)
需要注意的是当进行BFS时首次遇到其他颜色的点时如果当前点没被更新要全部放入队列里，这点是重点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define ls rt << 1
#define rs rt << 1|1
#define lson l, mid, ls
#define rson mid + 1, r, rs
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define pdd pair<double, double>
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn][maxn], f[45][maxn][maxn], vis[45];
vector<pii > e[maxn];
int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int n, m;
void bfs(int k)
{
    memset(vis, 0, sizeof(vis));
    queue<pii > Q;
    for(auto it : e[k]) Q.push(it);
    while(!Q.empty())
    {
        auto it = Q.front();
        Q.pop();
        if(!vis[a[it.fi][it.se]]) 
        {
            vis[a[it.fi][it.se]] = 1;
            for(auto p : e[a[it.fi][it.se]])
            {
                if(f[k][p.fi][p.se] != -1) continue;
                f[k][p.fi][p.se] = f[k][it.fi][it.se] + 1;
                Q.push(p);
            }
        }
        for(int i = 0; i < 4; ++i)
        {
            int x = it.fi + d[i][0], y = it.se + d[i][1];
            if(x < 1 || x > n || y < 1 || y > m || f[k][x][y] != -1)
                continue;
            f[k][x][y] = f[k][it.fi][it.se] + 1;
            Q.push({x, y});
        }
    }
}
int main()
{
    memset(f, -1, sizeof(f));
    int k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
            e[a[i][j]].push_back({i, j});
            f[a[i][j]][i][j] = 0;
        }
    }
    for(int i = 1; i <= k; ++i) bfs(i);
    int q1;
    scanf("%d", &q1);
    while(q1--)
    {
        int r1, c1, r2, c2;
        scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
        int ans = abs(r2 - r1) + abs(c2 - c1);
        for(int i = 1; i <= k; ++i)
        {
            ans = min(ans, f[i][r1][c1] + f[i][r2][c2] + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}