Advertisement
Guest User

Untitled

a guest
Nov 20th, 2018
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <math.h>
  5. #include <queue>
  6. typedef long long ll;
  7. #define nin(n) new int [(int)n]
  8. #define nis(n) new string [(int)n]
  9. #define npi(n) new pair<int, int>[(int)n]
  10. int oo = 0x3f3f3f3f;
  11.  
  12. using namespace std;
  13.  
  14. const int N = 200;
  15.  
  16.  
  17. char v1[N][N], v2[N][N];
  18.  
  19. int r1[4] = {-1, 0, 1, 0};
  20. int r2[4] = {0, 1, 0, -1};
  21. int r3[3] = {0, 1, 1};
  22. int r4[3] = {1, 1, 0};
  23. int a[N][N];
  24.  
  25. int main() {
  26. int n, m, d = 0;
  27. cin >> n >> m;
  28. for (int i = 0; i < n; ++i)
  29. {
  30. string s;
  31. cin >> s;
  32. for (int j = 0; j < m; ++j)
  33. v2[i][j] = s[j];
  34.  
  35. }
  36. for (int i = 0; i < n; ++i)
  37. {
  38. string s;
  39. cin >> s;
  40. for (int j = 0; j < m; ++j)
  41. v1[i][j] = s[j];
  42. }
  43.  
  44.  
  45. for (int i = 0; i < n; ++i)
  46. {
  47. for (int j = 0; j < m; ++j)
  48. {
  49. if (!isalpha(v2[i][j]))
  50. {
  51. if (v1[i][j] != v2[i][j])
  52. {
  53. cout << "NO";
  54. return 0;
  55. }
  56. }
  57. else if (!isalpha(v1[i][j]))
  58. {
  59. cout << "NO";
  60. return 0;
  61. }
  62. }
  63. }
  64.  
  65.  
  66. //--------------------BFS--------------------
  67. for (int x = 0; x < n; ++x)
  68. {
  69. for (int y = 0; y < m; ++y)
  70. {
  71. if (d == 1)
  72. break;
  73. if (!isalpha(v1[x][y]))
  74. {
  75. queue <pair <int, int>> q;
  76. q.push({x, y});
  77. a[x][y] = 1;
  78. int cur = 1;
  79. while (!q.empty()) {
  80. pair <int, int> p = q.front();
  81. q.pop();
  82. for (int i = 0; i < 4; ++i)
  83. {
  84. if (p.first + r1[i] < n && p.first + r1[i] >= 0 &&
  85. p.second + r2[i] < m && p.first + r2[i] >= 0)
  86. {
  87. if (a[p.first + r1[i]][p.second + r2[i]] == 0 &&
  88. v1[p.first + r1[i]][p.second + r2[i]] == 'w')
  89. {
  90. q.push({ p.first + r1[i], p.second + r2[i]});
  91. a[p.first + r1[i]][p.second + r2[i]] = 1;
  92. cur++;
  93. }
  94. }
  95. }
  96. }
  97. if (cur != v1[x][y] - 48)
  98. d = 1;
  99. }
  100. }
  101. }
  102.  
  103.  
  104. int t1 = -1, t2 = -1;
  105. for (int i = 0; i < n; ++i)
  106. {
  107. if (t1 != -1)
  108. break;
  109. for (int j = 0; j < n; ++j)
  110. {
  111. if (v1[i][j] == 'b')
  112. {
  113. t1 = i;
  114. t2 = j;
  115. break;
  116. }
  117. }
  118. }
  119.  
  120.  
  121. int x = t1, y = t2;
  122. bool lol = true, kek = true;
  123.  
  124.  
  125. //One more BFS
  126. queue <pair <int, int> > q;
  127. q.push({ x, y });
  128. a[x][y] = 1;
  129. while (!q.empty()) {
  130. pair <int, int> p = q.front();
  131. q.pop();
  132. for (int i = 0; i < 4; ++i)
  133. {
  134. if (p.first + r1[i] < n && p.first + r1[i] >= 0 &&
  135. p.second + r2[i] < m && p.first + r2[i] >= 0)
  136. {
  137. if (a[p.first + r1[i]][p.second + r2[i]] == 0 &&
  138. v1[p.first + r1[i]][p.second + r2[i]] == 'b')
  139. {
  140. q.push({ p.first + r1[i], p.second + r2[i]});
  141. a[p.first + r1[i]][p.second + r2[i]] = 1;
  142. }
  143. }
  144. }
  145. }
  146. for (int i = 0; i < n; ++i)
  147. {
  148. for (int j = 0; j < m; ++j)
  149. {
  150. if (a[i][j] == 0)
  151. {
  152. lol = false;
  153. break;
  154. }
  155. }
  156. }
  157. //End BFS
  158.  
  159.  
  160. for (int i = 0; i < n - 1; ++i)
  161. {
  162. for (int j = 0; j < m - 1; ++j)
  163. {
  164. int cur = 0;
  165. for (int k = 0; k < 3; ++k)
  166. {
  167. if (v1[i][j] == 'w' && v1[i][j] == v1[i + r3[k]][j + r4[k]])
  168. {
  169. cur++;
  170. }
  171. }
  172. if (cur == 4)
  173. {
  174. kek = false;
  175. break;
  176. }
  177. }
  178. }
  179. for (int i = 0; i < n; ++i)
  180. {
  181. for (int j = 0; j < m; ++j)
  182. {
  183. if (v1[i][j] == 'w' && a[i][j] == 0)
  184. {
  185. kek = false;
  186. break;
  187. }
  188. }
  189. }
  190.  
  191.  
  192. if (d == 1 || !kek || !lol)
  193. {
  194. cout << "NO";
  195. return 0;
  196. }
  197. cout << "YES";
  198. getchar();
  199. getchar();
  200. return 0;
  201. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement