环球关注：AtCoder Beginner Contest 289

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球关注：AtCoder Beginner Contest 289

2023-02-20 20:56:23 来源：博客园

(资料图片仅供参考)

E - Swap Places

题意

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

思路

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

代码

#include #include #include #include #include #include #include using namespace std;typedef pair pii;const int N = 2005;const int inf = 0x3f3f3f3f;int dp[N][N];int c[N];vector G[N];int n, m;void bfs() {    memset(dp, inf, sizeof(dp));    queue 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;}

关键词：时间复杂度不能相通