fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define endl "\n"
  6.  
  7. bool chk(vector<vector<bool>> &g) {
  8. 	int n = g.size(), m = g[0].size();
  9. 	bool flag = 1;
  10. 	for (int r = 0; r < n; ++r) {
  11. 		for (int c = 0; c < m; ++c) {
  12. 			if (!g[r][c]) {
  13. 				flag = 0;
  14. 				break;
  15. 			}
  16. 		}
  17. 	}
  18. 	return flag;
  19. }
  20.  
  21. bool solve(int i, int j, vector<vector<bool>> &g, vector<vector<int>> &ans) {
  22. 	int n = g.size(), m = g[0].size();
  23. 	cout << i << " " << j << endl;
  24. 	for (int a = 0; a < n; ++a) {
  25. 		for (int b = 0; b < m; ++b) {
  26. 			cout << g[a][b];
  27. 		}
  28. 		cout << " ";
  29. 		for (int b = 0; b < m; ++b) {
  30. 			cout << ans[a][b];
  31. 		}
  32. 		cout << endl;
  33. 	}
  34. 	cout << "----" << endl;
  35.  
  36. 	if (i == n) {
  37. 		return chk(g);
  38. 	}
  39.  
  40. 	int nexti, nextj;
  41. 	if (j+1 < m) {
  42. 		nexti = i;
  43. 		nextj = j+1;
  44. 	} else {
  45. 		nexti = i+1;
  46. 		nextj = 0;
  47. 	}
  48.  
  49. 	ans[i][j] = 1;
  50. 	bool f1 = solve(nexti, nextj, g, ans);
  51. 	if (f1) return 1;
  52.  
  53. 	ans[i][j] = 2;
  54. 	if (i-1 > 0) g[i-1][j] = !g[i-1][j];
  55. 	if (j-1 > 0) g[i][j-1] = !g[i][j-1];
  56. 	if (i+1 < n) g[i+1][j] = !g[i+1][j];
  57. 	if (j+1 < m) g[i][j+1] = !g[i][j+1];
  58. 	if (chk(g)) return 1;
  59. 	bool f2 = solve(nexti, nextj, g, ans);
  60. 	if (f2) return 1;
  61.  
  62. 	ans[i][j] = 3;
  63. 	g[i][j] = !g[i][j];
  64. 	if (chk(g)) return 1;
  65. 	bool f3 = solve(nexti, nextj, g, ans);
  66. 	if (f3) return 1;
  67.  
  68. 	if (!f2) {
  69. 		if (i-1 > 0) g[i-1][j] = !g[i-1][j];
  70. 		if (j-1 > 0) g[i][j-1] = !g[i][j-1];
  71. 		if (i+1 < n) g[i+1][j] = !g[i+1][j];
  72. 		if (j+1 < m) g[i][j+1] = !g[i][j+1];
  73. 		ans[i][j] = 2;
  74. 	}
  75.  
  76. 	if (!f3) {
  77. 		g[i][j] = !g[i][j];
  78. 		ans[i][j] = 3;
  79. 	}
  80.  
  81. 	return 0;
  82. }
  83.  
  84. int main() {
  85. 	int n, m;
  86. 	cin >> n >> m;
  87. 	vector<vector<bool>> g(n, vector<bool>(m));
  88. 	char c;
  89. 	for (int i = 0; i < n; ++i) {
  90. 		for (int j = 0; j < m; ++j) {
  91. 			cin >> c;
  92. 			g[i][j] = (c == 'W');
  93. 		}
  94. 	}
  95. 	vector<vector<int>> ans(n, vector<int>(m));
  96. 	bool f = solve(0, 0, g, ans);
  97. 	if (!f) {
  98. 		cout << -1 << endl;
  99. 	} else {
  100. 		cout << 1 << endl;
  101. 		for (int i = 0; i < n; ++i) {
  102. 			for (int j = 0; j < m; ++j) {
  103. 				cout << ans[i][j];
  104. 			}
  105. 			cout << endl;
  106. 		}
  107. 	}
  108.  
  109. 	return 0;
  110. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
2 3
WBW
BWB
stdout 
0 0
101 000
010 000
----
0 1
101 100
010 000
----
0 2
101 110
010 000
----
1 0
101 111
010 000
----
1 1
101 111
010 100
----
1 2
101 111
010 110
----
2 0
101 111
010 111
----
2 0
101 111
000 112
----
2 0
101 111
001 113
----
1 2
101 111
011 123
----
2 0
101 111
011 121
----
2 0
101 111
001 122
----
2 0
101 111
000 123
----
1 2
101 111
001 133
----
2 0
101 111
001 131
----
2 0
101 111
011 132
----
2 0
101 111
010 133
----
1 1
101 111
000 233
----
1 2
101 111
000 213
----
2 0
101 111
000 211
----
2 0
101 111
010 212
----
2 0
101 111
011 213
----
1 2
101 111
001 223
----
2 0
101 111
001 221
----
2 0
101 111
011 222
----
2 0
101 111
010 223
----
1 2
101 111
011 233
----
2 0
101 111
011 231
----
2 0
101 111
001 232
----
2 0
101 111
000 233
----
1 1
101 111
100 333
----
1 2
101 111
100 313
----
2 0
101 111
100 311
----
2 0
101 111
110 312
----
2 0
101 111
111 313
----
1 2
101 111
101 323
----
2 0
101 111
101 321
----
2 0
101 111
111 322
----
2 0
101 111
110 323
----
1 2
101 111
111 333
----
2 0
101 111
111 331
----
2 0
101 111
101 332
----
2 0
101 111
100 333
----
1 0
111 112
011 333
----
1 1
111 112
011 133
----
1 2
111 112
011 113
----
2 0
111 112
011 111
----
2 0
111 112
001 112
----
2 0
111 112
000 113
----
1 2
111 112
010 123
----
2 0
111 112
010 121
----
2 0
111 112
000 122
----
2 0
111 112
001 123
----
1 2
111 112
000 133
----
2 0
111 112
000 131
----
2 0
111 112
010 132
----
2 0
111 112
011 133
----
1 1
111 112
001 233
----
1 2
111 112
001 213
----
2 0
111 112
001 211
----
2 0
111 112
011 212
----
2 0
111 112
010 213
----
1 2
111 112
000 223
----
2 0
111 112
000 221
----
2 0
111 112
010 222
----
2 0
111 112
011 223
----
1 2
111 112
010 233
----
2 0
111 112
010 231
----
2 0
111 112
000 232
----
2 0
111 112
001 233
----
1 1
111 112
101 333
----
1 2
111 112
101 313
----
2 0
111 112
101 311
----
1
112
312
https://ideone.com/YII8DI
language:
C++14 (gcc 8.3)
created:
283 days 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!