Problem Statement
There is a grid with HH rows and WW columns. The cell at the ii-th row from the top and the jj-th column from the left is called cell (i,j)(i,j).
Every cell is colored white or black. The grid is described by HH strings S1,S2,…,SHS1,S2,…,S**H, each of length WW. If the jj-th character of SiS**i is ., cell (i,j)(i,j) is white; if the jj-th character of SiS**i is #, cell (i,j)(i,j) is black.
You perform the following operation 1010010100 times.
- Simultaneously apply the following rules to all cells.
- A cell that is white before the operation becomes black if and only if there exists at least one black cell adjacent to it. Here, cells (x,y)(x,y) and (x′,y′)(x′,y′) are adjacent if and only if one of them is within the 88-neighborhood of the other, that is, max(∣x−x′∣,∣y−y′∣)=1max(∣x−x′∣,∣y−y′∣)=1.
- A cell that is black before the operation becomes white.
Find the color of each cell after the operations.
Constraints
- 1≤H×W≤1061≤H×W≤106
- HH and WW are positive integers.
- SiS**i is a string of length WW consisting of
.and#.
Input
The input is given from Standard Input in the following format:
HH WW
S1S1
S2S2
⋮⋮
SHSH
Output
Output HH lines.
Output one string of length WW consisting of . and # per line.
The jj-th character of the ii-th line should be . if cell (i,j)(i,j) is white after 1010010100 operations, and # if it is black.
Sample 1
| Input复制 | Output复制 |
|---|---|
3 4 #.#. .#.. #... |
#.#. .#.. #..# |
Initially, the grid is as follows.
After one operation, the grid is as follows.
After 1010010100 operations, the grid is as follows.
Sample 2
| Input复制 | Output复制 |
|---|---|
3 3 ### ### ### |
... ... ... |
Sample 3
| Input复制 | Output复制 |
|---|---|
5 7 .#..... ....... ..#.... ....... ....#.. |
.#.##.# ....#.. #.#.### #.....# ###.#.# |
算法分析
这个题看似很难，实则非常的不简单，因为它的坑点很多，代码量也很大。
首先，直接模拟是不行的，因为如果要模拟的话，照题意，我们要模拟10^100次，肯定会炸。接着我们想一下，不（hen）难发现当一个点变成黑色时，之后每一次操作这个点都是黑白交替的，但是，如果你只想到这个那么恭喜你，成功的掉进了出题人的陷阱！很容易举出反例，比如题目中给出的样例二。我们仔细看一下样例二的输入，可以发现每个点并没有出现黑白交替，操作一次后，之后的每一次都是全白，因为每个点都被它周围一圈的黑点围着！但是，如果我们先操作一遍，那么就不可能出现一个黑点被它周围的黑点围着，因为我们只操作了一次呀！想到这一点后，我们已经成功了一半了，现在我们把思路整理一遍，以便写代码。
1.先手动模拟一次，时间复杂度是 O(nm)。
2.在已经做了一遍之后的数组上，对每个黑点都做一遍BFS。
3.有一个d数组，存的是每个点和离它最近的黑点的距离。
4.输出时如果d数组的一个点存的值是奇数，输出#，如果是偶数，输出 . 。
坑点
1.由于题目只给出了n*m，但没给出n和m的具体范围，所以每个数组都要开vector。
2.为了防止BFS死循环，要加判断再入队。
3.d数组记得初始化成极大值，且是偶数。
4.注意，这题有8个方向可以走，不要写成4个了。
5.在已经进行一次操作的数组上遍历到一个点是黑点时，千万不要急着去做BFS，先把这个点入队了，把d数组更新掉，等遍历完整个数组后，再统一BFS，否则会超时！！！
AC代码
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;int cnt;
};
int dx[] = {-1,-1,-1,0,0,1,1,1};//八个方向
int dy[] = {-1,0,1,-1,1,-1,0,1};
int n,m;
string a[1000005];
string b[1000005];
vector<int> d[1000005];//每个点和离它最近的黑点的距离
queue<node> q;
void bh(){//一次操作for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){if(a[i][j]=='#'){b[i][j] = '.';}else{bool flag = false;for(int k = 0; k<8; k++){int xx = dx[k]+i;int yy = dy[k]+j;if(xx>=1 && xx<=n && yy>=1 && yy<=m && a[xx][yy]=='#'){flag = true;b[i][j] = '#';break;}}if(flag==false){b[i][j] = '.';}}}}for(int i = 1; i<=n; i++){d[i].push_back(INT_MAX-1);for(int j = 1; j<=m; j++){a[i][j] = b[i][j];d[i].push_back(INT_MAX-1);//初始化为极大值，让它-1变成偶数}}
}
void bfs(){//BFSwhile(!q.empty()){node pos = q.front();q.pop();for(int i = 0; i<8; i++){int xx = dx[i]+pos.x;int yy = dy[i]+pos.y;if(xx>=1 && xx<=n && yy>=1 && yy<=m && d[xx][yy]>pos.cnt+1){//条件成立再入队和更新d[xx][yy] = pos.cnt+1;q.push(node{xx,yy,pos.cnt+1});}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//输入输出加速cin>>n>>m;for(int i = 1; i<=n; i++){string s;cin>>s;s = " "+s;//输入处理a[i] = s;b[i] = s;}bh();//先进行一次操作for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){if(a[i][j]=='#'){d[i][j] = 0;q.push(node{i,j,0});//先入队}}}bfs();//统一BFSfor(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){if(d[i][j]%2==1){cout<<'#';}else{cout<<'.';}}cout<<'\n';//比endl要快得多}return 0;
}