AtCoder Beginner Contest 289

E - Swap Places

题意

一个简单无向图，每一个点为黑白色的其中一种。
有2个人，x 在点 1，y 在点 n。
在每一步中，每个人都同时向相邻点移动，要求 2 人移动到的格子颜色不能相通。
问最少移动多少步可以使得 x 在点 n，y 在点 1。
数据规模为点数最多为 2000，边数最多为 2000。

思路

把2个人的位置当作二维坐标去考虑，开始在坐标 (1, n)，终点在 (n , 1)，求最少的移动步数。
用 bfs，在移动的时候判断 2 个下一个相邻点的颜色不同即可。
时间复杂度上限为 \(O(能过)\)。

代码

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdexcept>
using namespace std;
typedef pair<int, int> pii;
const int N = 2005;
const int inf = 0x3f3f3f3f;

int dp[N][N];
int c[N];

vector<int> G[N];
int n, m;

void bfs() {
    memset(dp, inf, sizeof(dp));
    queue<pii> q;
    q.push(pii(1, n));
    dp[1][n] = 0;
    while (!q.empty()) {
        if (dp[n][1] < inf) {
            break;
        }
        pii cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (const auto& u: G[x]) {
            for (const auto& v: G[y]) {
                if (c[u] == c[v]) {
                    continue;
                }
                if (dp[u][v] > dp[x][y] + 1) {
                    dp[u][v] = dp[x][y] + 1;
                    q.push(pii(u,v));
                }
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1;i <= n;i++) {
            cin >> c[i];
            G[i].clear();
        }
        for (int i = 0;i < m;i++) {
            int x, y;
            cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        bfs();
        cout << (dp[n][1] < inf ? dp[n][1] : -1) << endl;
    }
    return 0;
}