Advertisement
K_Y_M_bl_C

D

May 22nd, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. vector<vector<bool> > a;
  10. vector<vector<bool> > use;
  11. int dx[6] = {0, 0, 1, 1, -1, -1};
  12. int dy[6] = {1, -1, 0, -1, 1, 0};
  13. int n;
  14.  
  15. bool check(int x, int y) {
  16.     return x >= 0 && y >= 0 && x < n && y < n;
  17. }
  18.  
  19. bool dfs(int x, int y) {
  20.     if (x == n - 1)
  21.         return true;
  22.     use[x][y] = true;
  23.     for (int i = 0; i < 6; ++i) {
  24.         int new_x = x + dx[i];
  25.         int new_y = y + dy[i];
  26.         if (check(new_x, new_y) && !use[new_x][new_y] && a[new_x][new_y])
  27.             if (dfs(new_x, new_y))
  28.                 return true;
  29.     }
  30.     return false;
  31. }
  32.  
  33. int main() {
  34.     cin >> n;
  35.     a.resize(n);
  36.     for (int i = 0; i < n; ++i)
  37.         for (int j = 0; j < n; ++j) {
  38.             char p;
  39.             cin >> p;
  40.             if (p == 'W')
  41.                 a[i].push_back(true);
  42.             else
  43.                 a[i].push_back(false);
  44.         }
  45.     use = vector<vector<bool> >(n, vector<bool>(n, false));
  46.     for (int i = 0; i < n; ++i) {
  47.         if (!use[0][i] && a[0][i]) {
  48.             if (dfs(0, i)) {
  49.                 cout << "YES";
  50.                 return 0;
  51.             }
  52.         }
  53.     }
  54.     cout << "NO";
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement