Codeforces 525D Arthur and Walls

  1 // File Name: d.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年03月27日 星期五 16时05分31秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<cstdio>
 17 #include<cmath>
 18 #include<cstdlib>
 19 #include<ctime>
 20 #include<queue>
 21 #define LL long long
 22 
 23 using namespace std;
 24 int n ,m ;
 25 char mp[2005][2005];
 26 bool vis[2005][2005];
 27 struct  node{
 28     int x, y;
 29     node(){}
 30     node(int _x, int _y)
 31     {
 32         x = _x; 
 33         y = _y ;
 34     }
 35 }tmp;
 36 int lx, ly ,rx,ry;
 37 int xadd[] = {0,0,1,-1};
 38 int yadd[] = {1,-1,0,0};
 39 queue<node>qu;
 40 void solve(int tx,int ty)
 41 {
 42            mp[tx][ty] = ‘.‘;
 43            qu.push(node(tx,ty));
 44            for(int i = 0 ;i <= 3 ;i ++)
 45                qu.push(node(tx+xadd[i],ty+yadd[i]))    ;   
 46 }
 47 void bfs(int x,int y)
 48 {
 49       qu.push(node(x,y));
 50       int tx,ty;
 51       while(!qu.empty())
 52       {
 53          tmp = qu.front();
 54          qu.pop();
 55          if(mp[tmp.x][tmp.y] != ‘.‘)
 56              continue;
 57          if(mp[tmp.x-1][tmp.y] == ‘.‘ && mp[tmp.x][tmp.y+1] ==‘.‘ && mp[tmp.x-1][tmp.y+1] == ‘*‘)
 58          {
 59            tx = tmp.x -1;
 60            ty = tmp.y +1; 
 61            solve(tx,ty);
 62          }
 63          if(mp[tmp.x-1][tmp.y] == ‘.‘ && mp[tmp.x][tmp.y-1] ==‘.‘ && mp[tmp.x-1][tmp.y-1] == ‘*‘)
 64          {
 65            tx = tmp.x -1;
 66            ty = tmp.y -1; 
 67            solve(tx,ty);
 68          }
 69          if(mp[tmp.x+1][tmp.y] == ‘.‘ && mp[tmp.x][tmp.y+1] ==‘.‘ && mp[tmp.x+1][tmp.y+1] == ‘*‘)
 70          {
 71            tx = tmp.x +1;
 72            ty = tmp.y +1; 
 73            solve(tx,ty);
 74          }
 75          if(mp[tmp.x+1][tmp.y] == ‘.‘ && mp[tmp.x][tmp.y-1] ==‘.‘ && mp[tmp.x+1][tmp.y-1] == ‘*‘)
 76          {
 77            tx = tmp.x +1;
 78            ty = tmp.y -1; 
 79            solve(tx,ty);
 80          }
 81       }
 82 }
 83 int main(){
 84     scanf("%d %d",&n,&m);
 85     for(int i = 1;i <= n;i ++)
 86     {
 87         scanf("%s",&mp[i][1]);        
 88     }
 89     for(int i = 1 ;i <= n;i ++)
 90     {
 91         for(int j = 1;j <= m;j ++)
 92         {
 93             if( mp[i][j] == ‘.‘)
 94             {
 95                 bfs(i,j);
 96             }
 97         }
 98     }
 99     for(int i = 1;i <= n;i ++)
100         puts(&mp[i][1]);
101     return 0;
102 }