ARC 177
Table of Contents
A. Exchange
https://atcoder.jp/contests/arc177/tasks/arc177_a
B. Puzzle of Lamps
https://atcoder.jp/contests/arc177/tasks/arc177_b
C. Routing
https://atcoder.jp/contests/arc177/tasks/arc177_c
条件1について考える。赤色のマスを紫色に塗ってもスタートとゴールの連結性は変わらないから紫色に変えるべきマスは青色のマスである。 同様に条件2を達成するためには赤色のマスを紫色に変える必要がある。 よって条件1, 2を満たすために必要な紫色に変えるマスは独立して考えることができる。
よって問題の部分問題は次のように言い換えることができる。
各マスは赤か白で塗られており $c_{i,j} = 'R'$ のとき赤、$c_{i,j} = 'W'$ のとき白で塗られている。赤マス間は自由に行き来することできる。 スタートとゴールは赤マスである。 スタートとゴールが連結なるためには最低何マス追加で赤マスに変える必要があるか。
これを青マスについても同様に解いて、その和を求めればよい。
白マスへの移動はコスト $+1$、それ以外の移動は コスト $0$ であると考えると、スタートからゴールまでの最短経路を求める問題として解くことができる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<char>> B(n, vector<char>(n, '_')), R(n, vector<char>(n, '_'));
rep(i, n) {
rep(j, n) {
char c;
cin >> c;
if (c == 'R')
R[i][j] = c;
else
B[i][j] = c;
}
}
vint di = {1, 0, -1, 0};
vint dj = {0, -1, 0, 1};
auto cal = [&](vector<vector<char>>& grid, int si, int sj, int ti, int tj) -> ll {
vvll dist(n, vll(n, INF));
dist[si][sj] = 0;
using P = tuple<int, int, int>;
priority_queue<P, vector<P>, greater<P>> que;
que.push({0, si, sj});
while (que.size()) {
auto [cost, i, j] = que.top();
que.pop();
if (dist[i][j] < cost)
continue;
rep(d, 4) {
int ni = i + di[d], nj = j + dj[d];
if (clamp(ni, 0, n - 1) != ni || clamp(nj, 0, n - 1) != nj)
continue;
if (grid[ni][nj] == '_') {
if (dist[ni][nj] <= dist[i][j] + 1)
continue;
dist[ni][nj] = dist[i][j] + 1;
} else {
if (dist[ni][nj] <= dist[i][j])
continue;
dist[ni][nj] = dist[i][j];
}
que.push({dist[ni][nj], ni, nj});
}
}
return dist[ti][tj];
};
ll ans = cal(R, 0, 0, n - 1, n - 1) + cal(B, 0, n - 1, n - 1, 0);
cout << ans << endl;
}
D. Earthquakes
https://atcoder.jp/contests/arc177/tasks/arc177_d
E. Wrong Scoreboard
https://atcoder.jp/contests/arc177/tasks/arc177_e