P7479 【B】至曾是英雄的您 题解
本题解思路有别于与其他题解。 ### 简化版题意分析 白/黑棋快是由白/黑棋组成的连通块。 给您一副围棋黑棋块盘面，要求填上白棋块让黑棋块周围一格的空位都被填掉。 必须要保证周围一格没有空位白棋块的数量小于等于 $1$。 (这种题意可能会对未接触过围棋的选手~~我~~比较友好) ### 解法 我们先来讲一下总的做法：**找到所有需要填白棋的位置，判断这个位置的白棋块是否满足需求，填上白棋，计数，判断，输出答案。** 既然最终目标是填掉黑棋块周围一格的空位，那么我们首先要找到这一些空位。 这里我调用了一个函数 `checkLiberty` ```cpp // (liberty 是气的英文单词) // 使用字符串二维数组 a 记录棋盘，dx、dy 数组即为遍历当前位置周围一格的路径 // int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0}; // char a[2005][2005]; // 返回值 0 意为这里不是符合要求的空位，1 意为这里是符合要求的空位 inline int checkLiberty(int i, int j) { if (a[i][j] == '*' || a[i][j] == 'p') return 0; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) if (a[nx][ny] == '*') return 1; } return 0; } ``` 这里有一句 `a[i][j] == 'p'`，我们暂且一放，这个 `p` 会在下面用到。 我们先来看一下这段函数的作用。 如果当前位置是黑棋子，那么就返回 $0$。如果不是黑棋子，说明这里是空位，我们需要在周围一格找一下有没有黑棋子，如果有，那这个位置就是符合要求的空位。 找到了我们需要的空位，那么我们就要开始往这些空位里填白棋子了。 这里我调用了一个函数 `check`。 ```cpp // vis 数组记录走过的格子 // 返回值 0 意为这里无法按照题目要求放上白棋，1 意为这里可以 // 要求：这一白棋块周围至少有一个空位。 int check(int i, int j) { vis[i][j] = 1; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0) { if (a[nx][ny] == '.') if (checkLiberty(nx, ny) == 0) { vis[i][j] = 0; return 1; } else if (check(nx, ny) == 1) { vis[i][j] = 0; return 1; } } } vis[i][j] = 0; return 0; } ``` 我们先来看一下这段函数的作用。 对于这个位置，我们使用类似 DFS 的技巧，往外扩展搜索能让白棋合法放置的情况。 也就是说让这个位置放上白棋，之后一直往外铺，直到找到合适的空位能够让这个白棋放置成为合法的。 我们注意到这一段代码 ```cpp if (a[nx][ny] == '.') if (checkLiberty(nx, ny) == 0) { vis[i][j] = 0; return 1; } else if (check(nx, ny) == 1) { vis[i][j] = 0; return 1; } ``` 我们在搜索的时候搜到了空位，但是我们并不知道这个位置是不是黑棋块周围一格的空位（需要被填充的空位），所以我们需要判断。 调用 `checkLiberty` 函数，如果这里不是黑棋块周围一格的空位，那么我们在这个位置放上白棋就是符合的。 否则这里也要放上白棋，那么我们以这个新的白棋为起点，继续搜索。 这样搜索过后，我们就找到了白棋的情况。（周围没有合适的空位/周围有合适的空位） 我用一个 `cur` 变量来记录不符合要求的白棋块的数量，用于最终的结果判断。 找到情况之后，我调用了一个 `extendArea` 函数，用来把白棋填上。 ```cpp inline void extendArea(int i, int j) { a[i][j] = 'p'; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != 'p') if (checkLiberty(nx, ny) == 1) extendArea(nx, ny); } return; } ``` 因为这个位置所在的白棋块在 `check` 函数中已经被判定完了，所以我们就要把这个白棋所在的白棋块全部填上。 然后我们的 `p` 就出现了。 > 这里有一句 `a[i][j] == 'p'`，我们暂且一放，这个 `p` 会在下面用到。 > > ——来自于 `checkLiberty` 函数讲解部分。 我们可以回到这一句了，如果这个位置是一个白棋，那么这个位置肯定不是空位，所以返回为 $0$。 在判断 `cur` 和 $1$ 的关系后，我们就可以输出答案了。 **找到所有需要填白棋的位置，判断这个位置的白棋块是否满足需求，填上白棋，计数，判断，输出答案。** ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int n, m, t; char a[2005][2005]; int vis[2005][2005]; int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0}; inline int checkLiberty(int i, int j) { if (a[i][j] == '*' || a[i][j] == 'p') return 0; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) if (a[nx][ny] == '*') return 1; } return 0; } int check(int i, int j) { vis[i][j] = 1; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0) { if (a[nx][ny] == '.') if (checkLiberty(nx, ny) == 0) { vis[i][j] = 0; return 1; } else if (check(nx, ny) == 1) { vis[i][j] = 0; return 1; } } } vis[i][j] = 0; return 0; } inline void extendArea(int i, int j) { a[i][j] = 'p'; for (int k(0), nx, ny; k <= 3; ++k) { nx = i + dx[k]; ny = j + dy[k]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != 'p') if (checkLiberty(nx, ny) == 1) extendArea(nx, ny); } return; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> t; while (t--) { cin >> n >> m; for (int i(1); i <= n; ++i) cin >> (a[i] + 1); int cur = 0; for (int i(1); i <= n; ++i) for (int j(1); j <= m; ++j) if (checkLiberty(i, j)) { if (check(i, j) == 0) ++cur; extendArea(i, j); } if (cur <= 1) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } ```
<<< Return to archive list