题解 AT5798 【[AGC043A] Range Flip Find Route】
xht
2020-03-22 16:09:24
注意到，最后走的路线一定是黑白交替的。
每一次翻转颜色都一定是在进入黑色的时候，将后面一段黑色的路变成白色。
这与最短路很类似，由于边权只有 $0/1$，因此本题用 `deque` bfs 即可，时间复杂度 $\mathcal O(nm)$。
```cpp
const int N = 107, inf = 1e9;
int n, m, d[N][N], v[N][N];
char s[N][N];
deque<pi> q;
int main() {
rd(n), rd(m);
for (int i = 1; i <= n; i++) rds(s[i], m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] = inf;
q.pb(mp(1, 1)), d[1][1] = s[1][1] == '#';
while (q.size()) {
pi x = q.front();
q.pop_front();
if (v[x.fi][x.se]) continue;
v[x.fi][x.se] = 1;
if (x.fi < n) {
if (s[x.fi][x.se] == '.' && s[x.fi+1][x.se] == '#') {
if (d[x.fi+1][x.se] > d[x.fi][x.se] + 1)
q.pb(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se] + 1;
} else {
if (d[x.fi+1][x.se] > d[x.fi][x.se])
q.push_front(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se];
}
}
if (x.se < m) {
if (s[x.fi][x.se] == '.' && s[x.fi][x.se+1] == '#') {
if (d[x.fi][x.se+1] > d[x.fi][x.se] + 1)
q.pb(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se] + 1;
} else {
if (d[x.fi][x.se+1] > d[x.fi][x.se])
q.push_front(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se];
}
}
}
print(d[n][m]);
return 0;
}
```