xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 AT5798 【[AGC043A] Range Flip Find Route】

注意到,最后走的路线一定是黑白交替的。

每一次翻转颜色都一定是在进入黑色的时候,将后面一段黑色的路变成白色。

这与最短路很类似,由于边权只有 $0/1$,因此本题用 deque bfs 即可,时间复杂度 $\mathcal O(nm)$。

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;
}

2020-03-22 16:09:24 in 题解