fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. string a[101];
  10. int c[101][101], R, C, N;
  11. int dy[4]={0,0,1,-1}, dx[4]={1,-1,0,0};
  12. vector<pair<int,int>> group;
  13.  
  14. void dfs(int y, int x){
  15. 	if (a[y][x] == '.') return;
  16. 	if (c[y][x]) return;
  17. 	c[y][x] = true;
  18. 	group.push_back(make_pair(y,x));
  19. 	for(int k=0; k<4; k++){
  20. 		int ny = y+dy[k];
  21. 		int nx = x+dx[k];
  22. 		if(0 <= ny && ny < R && 0 <= nx && nx < C) dfs(ny,nx);
  23. 	}
  24. }
  25.  
  26. void simulate(){
  27. 	memset(c, false, sizeof(c));
  28. 	for(int y=0; y<R; y++){
  29. 		for (int x=0; x<C; x++){
  30. 			if (a[y][x] == '.') continue;
  31. 			if (c[y][x]) continue;
  32. 			group.clear();
  33. 			dfs(y,x);
  34. 			vector<int> low(C, -1);
  35. 			for(auto &p : group){
  36. 				low[p.second] = max(low[p.second], p.first);
  37. 				a[p.first][p.second] = '.';
  38. 			}
  39. 			int lowest = R;
  40. 			for(int i, j=0; j<C; j++){
  41. 				if (low[j] == -1) continue;
  42. 				for(i=low[j]; i<R && a[i][j]=='.'; i++);
  43. 				lowest = min(lowest, i-low[j]-1);
  44. 			}
  45. 			for(auto &p : group){
  46. 				p.first += lowest;
  47. 				a[p.first][p.second] = 'x';
  48. 				c[p.first][p.second] = true;
  49. 			}
  50. 		}
  51. 	}
  52. }
  53.  
  54. int main(){
  55. 	cin >> R >> C;
  56. 	for (int i=0; i<R; i++) cin >> a[i];
  57. 	cin >> N;
  58.  
  59. 	for(int i=0; i<N; i++){
  60. 		int h;
  61. 		cin >> h;
  62. 		h = R - h;
  63. 		if(i%2 == 0){
  64. 			for(int j=0; j<C; j++){
  65. 				if(a[h][j] == 'x'){
  66. 					a[h][j] = '.';
  67. 					break;
  68. 				}
  69. 			}
  70. 		}
  71. 		else{
  72. 			for(int j=C-1; j>=0; j--){
  73. 				if(a[h][j] == 'x'){
  74. 					a[h][j] = '.';
  75. 					break;
  76. 				}
  77. 			}
  78. 		}
  79. 		simulate();
  80. 	}
  81.  
  82. 	for(int i=0; i<R; i++){
  83. 		cout << a[i] << '\n';
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1
stdout
copy 
........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.
https://ideone.com/oYGQfi
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!