Time Lapse :1hour 37min 31sec
18500.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include <iostream> #include <algorithm> #include <memory.h> #include <queue> using namespace std; string map[100]; int h, w, n, cmd; int dx[4] = {0,1,0,-1}; int dy[4] = {-1,0,1,0}; bool motherV[100][100]; bool down(int y, int x) { if(y == h-1) return false; bool v[100][100]; memset(v,false,sizeof(v)); motherV[y][x] = v[y][x] = true; queue<pair<int,int>> q; q.push({y,x}); int maxMove = 987654321, i, j, k; while(!q.empty()) { pair<int,int> p = q.front(); q.pop(); for(i = 0; i < 4; i++) { int nx = p.second + dx[i]; int ny = p.first + dy[i]; if(0 <= nx && nx < w && 0 <= ny && ny < h && !v[ny][nx] && map[ny][nx] == 'x') { if(ny == h - 1 || motherV[ny][nx]) return false; motherV[ny][nx] = v[ny][nx] = true; q.push({ny,nx}); } } } for(i = 0; i < h - 1; i++) for(j = 0; j < w; j++) if(v[i][j] && !v[i+1][j]) { for(k = i + 1; k < h && map[k][j] == '.'; k++); if(k != h && v[k][j]) continue; maxMove = min(maxMove, (k-1)-i); } for(int i = h - 1; i >= 0; i--) for(int j = 0; j < w; j++) if(v[i][j]) { map[i][j] = '.'; map[i+maxMove][j] = 'x'; } return true; } void hit(int y, bool start) { int x = start ? w - 1 : 0; while(true) { if(x >= w || x < 0) return; if(map[y][x] == 'x') { map[y][x] = '.'; break; } start ? --x : ++x; } memset(motherV, false, sizeof(motherV)); for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] == 'x' && down(ny, nx)) return; } } int main() { scanf("%d %d",&h,&w); for(int i = 0; i < h; i++) cin>>map[i]; scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%d",&cmd); hit(h - cmd, i & 1); } for(int i = 0; i < h; i++) cout<<map[i]<<'\n'; }
|