洛谷

CF

分析

發現在一個邊長為 \(2\) 的聯通塊中，如果只有一個是*，就必須將其改變，然后 \(bfs\) 找就好了。

代碼

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;template <typename T> inline void read(T &x) {T f = 1; x = 0; char c;for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);x *= f;
}queue <P> q;int n, m;
int g[N][N];
char mp[N][N];bool check(int x, int y) {return g[x][y] + g[x+1][y] + g[x][y+1] + g[x+1][y+1] == 3;
}bool change(int x, int y) {if (g[x][y]) return false;if (check(x, y)) return true;if (x-1 > 0 && check(x-1, y)) return true;if (y-1 > 0 && check(x, y-1)) return true;if (x-1 > 0 && y-1 > 0 && check(x-1, y-1)) return true;return false;
}void bfs() {for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)if (change(i, j)) {g[i][j] = 1;q.push(make_pair(i, j));}while (!q.empty()) {P k = q.front(); q.pop();for (int i = k.first - 1; i <= k.first + 1; ++i)for (int j = k.second - 1; j <= k.second + 1; ++j)if (i > 0 && j > 0 && i <= n && j <= m && change(i, j)) {g[i][j] = 1;q.push(make_pair(i, j));}}
}int main() {read(n), read(m);for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) {cin >> mp[i][j];g[i][j] = (mp[i][j] == '.') ? 1 : 0;}bfs();for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) {if (g[i][j] == 1) putchar('.');else putchar('*');if (j == m) printf("\n");}return 0;
}

轉載于:https://www.cnblogs.com/hlw1/p/11503232.html

總結

以上是生活随笔為你收集整理的CF525D Arthur and Walls的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。