题解 [ABC213E]Stronger Takahashi

这场比赛两题都用了复杂的做法 “山路十八弯”,C 就一离散化被我搞得那么复杂,这 E 一简单 01 bfs 又被我整了个细节巨多的做法。

从 \((1, 1)\) 走到 \((n, m)\),只能走在 . 上不能走在 # 上,每次可以消掉 \(2 \times 2\) 的 #,求最少消掉几次才能到终点。

看到题就想到是某种神奇的建图方式然后给跑个最短路,然后略加思索就觉得是把每个联通块给标识出来以后在枚举每个 \(2 \times 2\) 进行爆破,看能把哪些连在一起。
写完了发现样例三这样要连续爆破的就过不了了,于是又把算法改成把单独的一个 # 也算作联通块进行处理。

可是这样一来就有大问题了,如这样:

..
##
##
##
##
##
..

若无脑把周围的都互相连上那么这本来要三次的就变成只要两次了。
而若无脑周围都不连,又会使一些两次的变成三次。

然后想来想去一直到比赛结束前最后五分钟才改出来一个连法,还自以为很妙:

  • \(2 \times 2\) 外面到里面的统统连上
  • 通向外面的 . 的连上
  • 否则一概不连

这样可以保证跨越两块的不会被过多或过少的计数。

冗长的代码
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define mapa std::make_pair
const int N = 505;
int n, m, col[N][N], dis[N*N], tot;
bool vis[N*N];
char map[N][N];
std::vector<int> g[N*N];
std::queue<int> q;
int dx[4] = {0, 0, -1, 1},
    dy[4] = {1, -1, 0, 0};
int bx[12] = {-1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2},
    by[12] = {0, 1, -1, 0, 1, 2, -1, 0, 1, 2, 0, 1},
    bf[12] = {1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1};
void color(int x, int y, int c) {
    col[x][y] = c;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m 
            || map[xx][yy] == '#' || col[xx][yy]) continue;
        color(xx, yy, c);
    }
}
void bfs(int s) {
    q.push(s); vis[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (vis[v]) continue;
            dis[v] = dis[u] + 1;
            vis[v] = 1;
            q.push(v);
        }
    }
}
int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        std::cin >> (map[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            if (map[i][j] == '.' && !col[i][j])
                color(i, j, ++tot);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (map[i][j] == '#') col[i][j] = ++tot;
    for (int i = 1; i <= n-1; i++)
        for (int j = 1; j <= m-1; j++) {
            std::vector<std::pair<int, std::pair<bool, bool> > > tmp;
            for (int k = 0; k < 12; k++) {
                int xx = i + bx[k], yy = j + by[k];
                if (xx < 1 || xx > n || yy < 1 || yy > m)
                    continue;
                tmp.push_back(mapa(col[xx][yy], mapa(bf[k], map[xx][yy] == '#')));
            }
            for (int a = 0; a < (int)tmp.size(); a++)
                for (int b = 0; b < (int)tmp.size(); b++) {
                    int u = tmp[a].first, v = tmp[b].first;
                    if ((tmp[a].second.first && !tmp[b].second.first) || !tmp[b].second.second) 
                        g[u].push_back(v);
                }
        }
    bfs(col[1][1]);
    std::cout << dis[col[n][m]];
}

赛后看了题解。
发现这题非常简单啊!

一个点爆破一次可以到这些点

.***.
*****
**T**
*****
.***.

那么 01bfs 即可。

简洁的代码
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#define mapa std::make_pair
const int N = 505;
int n, m, vis[N][N], dis[N][N];
char map[N][N];
std::deque<std::pair<int, int> > q;
int dx[20] = {0, 0, 1, -1, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2},
    dy[20] = {-1, 1, 0, 0, -1, 0, 1, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -1, 0, 1};
bool check(int x, int y) { return x < 1 || x > n || y < 1 || y > m; }
void bfs(int x, int y) {
    q.push_back(mapa(x, y));
    memset(dis, 0x3f, sizeof dis);
    dis[x][y] = 0;
    while (!q.empty()) {
        x = q.front().first, y = q.front().second, q.pop_front();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (check(xx, yy) || map[xx][yy] == '#') continue;
            dis[xx][yy] = std::min(dis[xx][yy], dis[x][y]), q.push_front(mapa(xx, yy));
        }
        for (int i = 0; i < 20; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (check(xx, yy)) continue;
            dis[xx][yy] = std::min(dis[xx][yy], dis[x][y]+1), q.push_back(mapa(xx, yy));
        }
    }
}
int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
        std::cin >> (map[i]+1);
    bfs(1, 1);
    std::cout << dis[n][m];
}

又好写又跑得快。

那么问题出在哪里使我没能想到这样子的简单的做法呢?
说道底还是不愿仔细模拟和观察性质的老问题没有解决。

上一篇:PostgreSQL安装手册(Centos7)


下一篇:Postgres-XC