Advertisement
ayrefky

Untitled

Dec 2nd, 2022
600
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     bool isValid(int i, int j, vector<vector<char>>& board) {
  4.         return i >= 0 and i < board.size() and j >= 0 and j < board[0].size() and board[i][j] == 'O';
  5.     }
  6.     bool isBorder(int i, int j, vector<vector<char>>& board) {
  7.         return i == 0 or j == 0 or i == board.size() - 1 or j == board[0].size() - 1;
  8.     }
  9.     void dfs(int i, int j, vector<vector<char>>& board, set<pair<int, int>>& visited, set<pair<int, int>>& curr_visited) {
  10.         if(!isValid(i, j, board) or visited.find({i, j}) != visited.end()) return;
  11.         if(isBorder(i, j, board)) {
  12.             for(auto element : curr_visited) {
  13.                 int x = element.first;
  14.                 int y = element.second;
  15.                 board[x][y] = 'O';
  16.             }
  17.             return;
  18.         }
  19.         visited.insert({i, j});
  20.         curr_visited.insert({i, j});
  21.         board[i][j] = 'X';
  22.         vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  23.         for(auto dir : dirs) {
  24.             int dx = i + dir.first;
  25.             int dy = j + dir.second;
  26.             dfs(dx, dy, board, visited, curr_visited);
  27.         }
  28.     }
  29.     void solve(vector<vector<char>>& board) {
  30.         set<pair<int, int>> visited;
  31.         for(int i = 0; i < board.size(); i++) {
  32.             for(int j = 0; j < board[0].size(); j++) {
  33.                 if(board[i][j] == 'O') {
  34.                     set<pair<int, int>> curr_visited;
  35.                     dfs(i, j, board, visited, curr_visited);
  36.                 }
  37.             }
  38.         }
  39.     }
  40. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement