Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <math.h>
- #include <queue>
- typedef long long ll;
- #define nin(n) new int [(int)n]
- #define nis(n) new string [(int)n]
- #define npi(n) new pair<int, int>[(int)n]
- int oo = 0x3f3f3f3f;
- using namespace std;
- const int N = 200;
- char v1[N][N], v2[N][N];
- int r1[4] = {-1, 0, 1, 0};
- int r2[4] = {0, 1, 0, -1};
- int r3[3] = {0, 1, 1};
- int r4[3] = {1, 1, 0};
- int a[N][N];
- int main() {
- int n, m, d = 0;
- cin >> n >> m;
- for (int i = 0; i < n; ++i)
- {
- string s;
- cin >> s;
- for (int j = 0; j < m; ++j)
- v2[i][j] = s[j];
- }
- for (int i = 0; i < n; ++i)
- {
- string s;
- cin >> s;
- for (int j = 0; j < m; ++j)
- v1[i][j] = s[j];
- }
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (!isalpha(v2[i][j]))
- {
- if (v1[i][j] != v2[i][j])
- {
- cout << "NO";
- return 0;
- }
- }
- else if (!isalpha(v1[i][j]))
- {
- cout << "NO";
- return 0;
- }
- }
- }
- //--------------------BFS--------------------
- for (int x = 0; x < n; ++x)
- {
- for (int y = 0; y < m; ++y)
- {
- if (d == 1)
- break;
- if (!isalpha(v1[x][y]))
- {
- queue <pair <int, int>> q;
- q.push({x, y});
- a[x][y] = 1;
- int cur = 1;
- while (!q.empty()) {
- pair <int, int> p = q.front();
- q.pop();
- for (int i = 0; i < 4; ++i)
- {
- if (p.first + r1[i] < n && p.first + r1[i] >= 0 &&
- p.second + r2[i] < m && p.first + r2[i] >= 0)
- {
- if (a[p.first + r1[i]][p.second + r2[i]] == 0 &&
- v1[p.first + r1[i]][p.second + r2[i]] == 'w')
- {
- q.push({ p.first + r1[i], p.second + r2[i]});
- a[p.first + r1[i]][p.second + r2[i]] = 1;
- cur++;
- }
- }
- }
- }
- if (cur != v1[x][y] - 48)
- d = 1;
- }
- }
- }
- int t1 = -1, t2 = -1;
- for (int i = 0; i < n; ++i)
- {
- if (t1 != -1)
- break;
- for (int j = 0; j < n; ++j)
- {
- if (v1[i][j] == 'b')
- {
- t1 = i;
- t2 = j;
- break;
- }
- }
- }
- int x = t1, y = t2;
- bool lol = true, kek = true;
- //One more BFS
- queue <pair <int, int> > q;
- q.push({ x, y });
- a[x][y] = 1;
- while (!q.empty()) {
- pair <int, int> p = q.front();
- q.pop();
- for (int i = 0; i < 4; ++i)
- {
- if (p.first + r1[i] < n && p.first + r1[i] >= 0 &&
- p.second + r2[i] < m && p.first + r2[i] >= 0)
- {
- if (a[p.first + r1[i]][p.second + r2[i]] == 0 &&
- v1[p.first + r1[i]][p.second + r2[i]] == 'b')
- {
- q.push({ p.first + r1[i], p.second + r2[i]});
- a[p.first + r1[i]][p.second + r2[i]] = 1;
- }
- }
- }
- }
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (a[i][j] == 0)
- {
- lol = false;
- break;
- }
- }
- }
- //End BFS
- for (int i = 0; i < n - 1; ++i)
- {
- for (int j = 0; j < m - 1; ++j)
- {
- int cur = 0;
- for (int k = 0; k < 3; ++k)
- {
- if (v1[i][j] == 'w' && v1[i][j] == v1[i + r3[k]][j + r4[k]])
- {
- cur++;
- }
- }
- if (cur == 4)
- {
- kek = false;
- break;
- }
- }
- }
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (v1[i][j] == 'w' && a[i][j] == 0)
- {
- kek = false;
- break;
- }
- }
- }
- if (d == 1 || !kek || !lol)
- {
- cout << "NO";
- return 0;
- }
- cout << "YES";
- getchar();
- getchar();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement