# ARC117-C Routing

1055diff
https://atcoder.jp/contests/arc177/tasks/arc177_c

## 解法

条件1を達成するために変更すべきマスは青いマスのみである。
また、どの青マスを紫マスに変えた所で、条件2にとって不利になることはない

条件2を達成するために変更すべきマスは赤いマスのみである。
また、どの赤マスを紫マスに変えた所で、条件1にとって不利になることはない

以上より「条件1を達成するために紫マスに変更する青マスの最小個数は？」と「条件2を達成するために紫マスに変更する赤マスの最小個数は？」を独立に解けばよく、どちらとも01BFSでできる。

## 実装

#include <bits/stdc++.h>

const int dx[4]{ 0, 1, 0, -1 }, dy[4]{ 1, 0, -1, 0 };

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    std::cin >> N;
    std::vector<std::string> S(N);
    for (auto& s : S) std::cin >> s;

    auto in{[&](int x, int y) -> bool {
        return 0 <= x and x < N and 0 <= y and y < N;
    }};

    auto bfs{[&](int sx, int sy, int gx, int gy, char ok) -> int {
        const int INF{(int)1e9};
        std::vector dist(N, std::vector<int>(N, INF));
        dist[sx][sy] = 0;
        std::deque<std::pair<int, int>> deq;
        deq.push_back(std::pair{sx, sy});
        while (deq.size()) {
            auto [x, y]{deq.front()};
            deq.pop_front();
            for (int d{} ; d < 4 ; d++) {
                int nx{x + dx[d]}, ny{y + dy[d]};
                if (!in(nx, ny)) continue;
                int w{S[nx][ny] == ok ? 0 : 1};
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    if (w) deq.push_back(std::pair{ nx, ny });
                    else deq.push_front(std::pair{ nx, ny });
                }
            }
        }
        return dist[gx][gy];
    }};

    std::cout << bfs(0, 0, N - 1, N - 1, 'R') + bfs(0, N - 1, N - 1, 0, 'B') << '\n';
}

[提出](https://atcoder.jp/contests/arc177/submissions/58160815)

## 感想

昔解説を開いた記憶があって、本質パートを記憶したままだった....