# Leetcode 130 Solution

https://leetcode.com/problems/surrounded-regions

## Solution

class Solution {
int m;
int n;
public:
void mark(vector<vector<char>>& board, int y, int x)
{
queue<pair<int, int>> q;

board[y][x] = 'P';
q.push(make_pair(y, x));

while (q.empty() == false)
{
auto pair = q.front();
q.pop();

int i = pair.first;
int j = pair.second;

if (i > 0 && board[i - 1][j] == 'O')
board[i - 1][j] = 'P', q.push(make_pair(i - 1, j));

if (i < m - 1 && board[i + 1][j] == 'O')
board[i + 1][j] = 'P', q.push(make_pair(i + 1, j));

if (j > 0 && board[i][j - 1] == 'O')
board[i][j - 1] = 'P', q.push(make_pair(i, j - 1));

if (j < n - 1 && board[i][j + 1] == 'O')
board[i][j + 1] = 'P', q.push(make_pair(i, j + 1));
}
}

void solve(vector<vector<char>>& board)
{
m = board.size();
if (m == 0)
return;
n = board[0].size();

for (int i = 0; i < m; i++)
{
if (board[i][0] == 'O')
mark(board, i, 0);

if (board[i][n - 1] == 'O')
mark(board, i, n - 1);
}

for (int j = 0; j < n; j++)
{
if (board[0][j] == 'O')
mark(board, 0, j);

if (board[m - 1][j] == 'O')
mark(board, m - 1, j);
}

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'O')
board[i][j] = 'X';

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'P')
board[i][j] = 'O';
}
};