Valkyrie006

Untitled

Oct 23rd, 2021 (edited)
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. int n, m;
  2.  
  3. void dfs(vector<vector<char>> &board, int x, int y, int d, vector<vector<vector<bool>>> &visited)
  4. {
  5.  
  6.     if (x == n || x == -1 || y == -1 || y == m)
  7.     {
  8.         if (x == n)
  9.         {
  10.             dfs(board, x - 1, y, 2, visited);
  11.         }
  12.         else if (x == -1)
  13.         {
  14.             dfs(board, x + 1, y, 0, visited);
  15.         }
  16.         else if (y == m)
  17.         {
  18.             dfs(board, x, y - 1, 1, visited);
  19.         }
  20.         else if (y == -1)
  21.         {
  22.             dfs(board, x, y + 1, 3, visited);
  23.         }
  24.         return;
  25.     }
  26.     if (visited[x][y][d])
  27.     {
  28.         return;
  29.     }
  30.     visited[x][y][d] = true;
  31.     if (board[x][y] != 'X')
  32.     {
  33.         if (d == 0)
  34.         {
  35.             dfs(board, x, y + 1, 0, visited);
  36.         }
  37.         else if (d == 1)
  38.         {
  39.             dfs(board, x + 1, y, 1, visited);
  40.         }
  41.         else if (d == 2)
  42.         {
  43.             dfs(board, x, y - 1, 2, visited);
  44.         }
  45.         else
  46.         {
  47.             dfs(board, x - 1, y, 3, visited);
  48.         }
  49.     }
  50.     else
  51.     {
  52.         if (d == 0)
  53.         {
  54.             dfs(board, x, y - 1, 1, visited);
  55.         }
  56.         else if (d == 1)
  57.         {
  58.             dfs(board, x - 1, y, 2, visited);
  59.         }
  60.         else if (d == 2)
  61.         {
  62.             dfs(board, x, y + 1, 3, visited);
  63.         }
  64.         else
  65.         {
  66.             dfs(board, x + 1, y, 0, visited);
  67.         }
  68.     }
  69. }
  70.  
  71. void solve()
  72. {
  73.     cin >> n >> m;
  74.     vector<vector<char>> board(n, vector<char>(m));
  75.     for (int i = 0; i < n; i++)
  76.     {
  77.         for (int j = 0; j < m; j++)
  78.         {
  79.             cin >> board[i][j];
  80.         }
  81.     }
  82.     vector<vector<vector<bool>>> visited(n, vector<vector<bool>>(m, vector<bool>(4, false)));
  83.     dfs(board, 0, 0, 0, visited);
  84.     int ans = 0;
  85.     for (int i = 0; i < n; i++)
  86.     {
  87.         for (int j = 0; j < m; j++)
  88.         {
  89.             if (board[i][j] == 'X')
  90.                 continue;
  91.             bool isVisited = false;
  92.             for (int d = 0; d < 4; d++)
  93.             {
  94.                 isVisited |= visited[i][j][d];
  95.             }
  96.             ans += (isVisited == true);
  97.         }
  98.     }
  99.     cout << ans << endl;
  100.     return;
  101. }
Add Comment
Please, Sign In to add comment