Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- bool isValid(int i, int j, vector<vector<char>>& board) {
- return i >= 0 and i < board.size() and j >= 0 and j < board[0].size() and board[i][j] == 'O';
- }
- bool isBorder(int i, int j, vector<vector<char>>& board) {
- return i == 0 or j == 0 or i == board.size() - 1 or j == board[0].size() - 1;
- }
- void dfs(int i, int j, vector<vector<char>>& board, set<pair<int, int>>& visited, set<pair<int, int>>& curr_visited) {
- if(!isValid(i, j, board) or visited.find({i, j}) != visited.end()) return;
- if(isBorder(i, j, board)) {
- for(auto element : curr_visited) {
- int x = element.first;
- int y = element.second;
- board[x][y] = 'O';
- }
- return;
- }
- visited.insert({i, j});
- curr_visited.insert({i, j});
- board[i][j] = 'X';
- vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
- for(auto dir : dirs) {
- int dx = i + dir.first;
- int dy = j + dir.second;
- dfs(dx, dy, board, visited, curr_visited);
- }
- }
- void solve(vector<vector<char>>& board) {
- set<pair<int, int>> visited;
- for(int i = 0; i < board.size(); i++) {
- for(int j = 0; j < board[0].size(); j++) {
- if(board[i][j] == 'O') {
- set<pair<int, int>> curr_visited;
- dfs(i, j, board, visited, curr_visited);
- }
- }
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement