题目地址：Arthur and Walls 这题有一个脑洞，对于当前的点(i,j)并且此点为”*”来说，若存在包含它的2*2正方形中除了它自己外，另外三个点都是”.”，，那么这个点就必须要变成”.”。由于去掉这个点之后会对周围的8个点造成影响，所以可以用BFS去搜。WA第12组的应该是只考虑了会影响到周围的4个点了。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=40000+10;char mp[2015][2015];int n, m;int jx[]={0,0,1,-1,1,-1,1,-1};int jy[]={1,-1,0,0,1,-1,-1,1};bool check(int x, int y){if(x<0||x>n||y<0||y>m) return false;if(mp[x][y]==’.’) return true;return false;}bool Judge(int x, int y){if(mp[x][y]!=’*’) return false;if(check(x+1,y)&&check(x+1,y+1)&&check(x,y+1)) return true;if(check(x+1,y)&&check(x+1,y-1)&&check(x,y-1)) return true;if(check(x-1,y)&&check(x-1,y+1)&&check(x,y+1)) return true;if(check(x,y-1)&&check(x-1,y-1)&&check(x-1,y)) return true;return false;}queue<pair<int,int> >q;void bfs(){int i, x, y, a, b;while(!q.empty()){x=q.front().first;y=q.front().second;q.pop();if(mp[x][y]==’.’) continue ;mp[x][y]=’.’;for(i=0;i<8;i++){a=x+jx[i];b=y+jy[i];if(a>=0&&a<n&&b>=0&&b<m&&Judge(a,b)){q.push(make_pair(a,b));}}}}int main(){int i, j;while(scanf(“%d%d”,&n,&m)!=EOF){for(i=0;i<n;i++){scanf(“%s”,mp[i]);}for(i=0;i<n;i++){for(j=0;j<m;j++){if(Judge(i,j))q.push(make_pair(i,j));}}bfs();for(i=0;i<n;i++){printf(“%s\n”,mp[i]);}}return 0;}
环境不会改变，解决之道在于改变自己。
