fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using lint = long long;
  4. using pi = pair<int, int>;
  5. const int MAXN = 10005;
  6. const int mod = 1e9 + 7;
  7.  
  8. struct disj{
  9. 	int pa[MAXN];
  10. 	void init(int n){
  11. 		iota(pa, pa + n + 1, 0);
  12. 	}
  13. 	int find(int x){
  14. 		return pa[x] = (pa[x] == x ? x : find(pa[x]));
  15. 	}
  16. 	bool uni(int p, int q){
  17. 		p = find(p);
  18. 		q = find(q);
  19. 		if(p == q) return 0;
  20. 		pa[q] = p; return 1;
  21. 	}
  22. }disj;
  23.  
  24. int K;
  25. pi a[MAXN][2];
  26. int chk[MAXN][2];
  27. pi par[MAXN][2];
  28. namespace graph{
  29. 	vector<pi> gph[10005];
  30. 	int par[10005], pae[10005];
  31. 	void dfs(int x, int p){
  32. 		for(auto &i : gph[x]){
  33. 			if(i.second != p){
  34. 				par[i.second] = x;
  35. 				pae[i.second] = i.first;
  36. 				dfs(i.second, x);
  37. 			}
  38. 		}
  39. 	}
  40.  
  41. 	void clear(){
  42. 		for(int i=0; i<K; i++){
  43. 			for(int j=0; j<2; j++){
  44. 				gph[a[i][j].first].clear();
  45. 				gph[a[i][j].second].clear();
  46. 				par[a[i][j].first] = -1;
  47. 				par[a[i][j].second] = -1;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	vector<pi> inCycle(pi x){
  53. 		for(int i=0; i<K; i++){
  54. 			for(int j=0; j<2; j++){
  55. 				if(chk[i][j]){
  56. 					int w = i * 2 + j;
  57. 					int l = a[i][j].first;
  58. 					int r = a[i][j].second;
  59. 					gph[l].emplace_back(w, r);
  60. 					gph[r].emplace_back(w, l);
  61. 				}
  62. 			}
  63. 		}
  64. 		dfs(x.first, -1);
  65. 		if(par[x.second] == -1){
  66. 			clear();
  67. 			return vector<pi>();
  68. 		}
  69. 		vector<pi> ret;
  70. 		for(int y = x.second; y != x.first; y = par[y]){
  71. 			ret.emplace_back(pae[y] / 2, pae[y] % 2);
  72. 		}
  73. 		clear();
  74. 		return ret;
  75. 	}
  76. }
  77.  
  78. const int dx[4] = {1, 0, -1, 0};
  79. const int dy[4] = {0, 1, 0, -1};
  80.  
  81. int n, m;
  82. char str[105][105];
  83. int vis[105][105];
  84.  
  85. bool ok(int x, int y){ return 0 <= x && x < n && 0 <= y && y < m; }
  86.  
  87. void dfs(int x, int y, int c){
  88. 	vis[x][y] = c;
  89. 	for(int i=0; i<4; i++){
  90. 		if(ok(x + dx[i], y + dy[i]) && 
  91. 			!vis[x + dx[i]][y + dy[i]] && 
  92. 			str[x][y] == str[x + dx[i]][y + dy[i]]){
  93. 			dfs(x + dx[i], y + dy[i], c);
  94. 		}
  95. 	}
  96. }
  97.  
  98. char dap[105][105];
  99.  
  100. int main(){
  101. 	int tc;
  102. 	scanf("%d",&tc);
  103. 	memset(graph::par, -1, sizeof(graph::par));
  104. 	for(int i=1; i<=tc; i++){
  105. 		memset(vis, 0, sizeof(vis));
  106. 		memset(chk, 0, sizeof(chk));
  107. 		memset(dap, 0, sizeof(dap));
  108. 		int cnt = 0;
  109. 		scanf("%d %d",&n,&m);
  110. 		for(int i=0; i<n; i++) scanf("%s", str[i]);
  111. 		for(int i=0; i<n; i++){
  112. 			for(int j=0; j<m; j++){
  113. 				if(!vis[i][j]){
  114. 					++cnt;
  115. 					dfs(i, j, cnt);
  116. 				}
  117. 			}
  118. 		}
  119. 		if(cnt == 1){
  120. 			printf("Case #%d: POSSIBLE\n", i);
  121. 			for(int i=0; i<n-1; i++){
  122. 				for(int j=0; j<m-1; j++) putchar('/');
  123. 				puts("");
  124. 			}
  125. 			continue;
  126. 		}
  127. 		int answ = 0;
  128. 		disj.init(n * m);
  129. 		for(int i=1; i<n; i++){
  130. 			for(int j=1; j<m; j++){
  131. 				if(str[i-1][j-1] == str[i][j] && str[i-1][j] == str[i][j-1]){
  132. 					continue;
  133. 				}
  134. 				if(str[i-1][j-1] != str[i][j] && str[i-1][j] != str[i][j-1]){
  135. 					dap[i-1][j-1] = '.';
  136. 				}
  137. 				else if(str[i-1][j-1] != str[i][j]){
  138. 					dap[i-1][j-1] = '/';
  139. 					answ += disj.uni(vis[i-1][j], vis[i][j-1]);
  140.  
  141. 				}
  142. 				else{
  143. 					dap[i-1][j-1] = '\\';
  144. 					answ += disj.uni(vis[i-1][j-1], vis[i][j]);
  145. 				}
  146. 			}
  147. 		}
  148. 		K = 0;
  149. 		for(int i=1; i<n; i++){
  150. 			for(int j=1; j<m; j++){
  151. 				if(dap[i-1][j-1]) continue;
  152. 				int s1 = disj.find(vis[i-1][j-1]);
  153. 				int e1 = disj.find(vis[i][j]);
  154. 				int s2 = disj.find(vis[i-1][j]);
  155. 				int e2 = disj.find(vis[i][j-1]);
  156. 				a[K][0] = pi(s1, e1);
  157. 				a[K][1] = pi(s2, e2);
  158. 				K++;
  159. 			}
  160. 		}
  161. 		for(int i=0; i<K; i++){
  162. 			bool vis[MAXN][2] = {};
  163. 			queue<pi> que;
  164. 			for(int j=0; j<2; j++){
  165. 				que.emplace(i, j);
  166. 				vis[i][j] = 1;
  167. 				par[i][j] = pi(-1, -1);
  168. 			}
  169. 			while(!que.empty()){
  170. 				auto x = que.front();
  171. 				que.pop();
  172. 				if(chk[x.first][x.second] == 0){
  173. 					auto edg = a[x.first][x.second];
  174. 					if(edg.first == edg.second) continue;
  175. 					auto adj = graph::inCycle(edg);
  176. 					if(adj.empty()){
  177. 						for(pi i = x; i != pi(-1, -1); i = par[i.first][i.second]){
  178. 							chk[i.first][i.second] ^= 1;
  179. 						}
  180. 						answ++;
  181. 						break;
  182. 					}
  183. 					else{
  184. 						for(auto &y : adj){
  185. 							if(!vis[y.first][y.second]){
  186. 								vis[y.first][y.second] = 1;
  187. 								par[y.first][y.second] = x;
  188. 								que.push(y);
  189. 							}
  190. 						}
  191. 					}
  192. 				}
  193. 				else{
  194. 					if(!vis[x.first][x.second^1]){
  195. 						vis[x.first][x.second^1] = 1;
  196. 						par[x.first][x.second^1] = x;
  197. 						que.emplace(x.first, x.second ^ 1);
  198. 					}
  199. 				}
  200. 			}
  201. 		}
  202. 		if(answ + 2 < cnt){
  203. 			printf("Case #%d: IMPOSSIBLE\n", i);
  204. 			continue;
  205. 		}
  206. 		else{
  207. 			printf("Case #%d: POSSIBLE\n", i);
  208. 			int L = 0;
  209. 			for(int i=1; i<n; i++){
  210. 				for(int j=1; j<m; j++){
  211. 					if(dap[i-1][j-1]) continue;
  212. 					if(chk[L][0]){
  213. 						dap[i-1][j-1] = '\\';
  214. 					}
  215. 					else if(chk[L][1]){
  216. 						dap[i-1][j-1] = '/';
  217. 					}
  218. 					else{
  219. 						dap[i-1][j-1] = '.';
  220. 					}
  221. 					L++;
  222. 				}
  223. 				puts(dap[i-1]);
  224. 			}
  225. 		}
  226. 	}
  227. }
  228.  
  229.  
Success #stdin #stdout 0s 16048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/n14QX5
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!