Leetcode Surrounded Regions

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char> > &board) {
 4         if (board.size() == 0) return;
 5         int my = board.size() - 1;
 6         int mx = board[0].size() -1;
 7         // top border
 8         for (int i=0; i<=mx; i++) {
 9             bfs(board, mx, my, i, 0, ‘O‘, ‘+‘);
10         }
11         // bottom border
12         for (int i=0; i<=mx; i++) {
13             bfs(board, mx, my, i, my, ‘O‘, ‘+‘);
14         }
15         // left border
16         for (int i=0; i<=my; i++) {
17             bfs(board, mx, my, 0, i, ‘O‘, ‘+‘);
18         }
19         // right border
20         for (int i=0; i<=my; i++) {
21             bfs(board, mx, my, mx, i, ‘O‘, ‘+‘);
22         }
23         
24         // scan & fill
25         for (int i=1; i<=my-1; i++) {
26             for (int j=1; j<=mx-1; j++) {
27                 if (board[i][j] == ‘O‘) board[i][j] = ‘X‘;
28             }
29         }
30         
31         // restore
32         for (int i=0; i<=my; i++) {
33             for (int j=0; j<=mx; j++) {
34                 if (board[i][j] == ‘+‘) board[i][j] = ‘O‘;
35             }
36         }
37     }
38     
39     void bfs(vector<vector<char> >& board, int mx, int my, int _x, int _y, char oc, char nc) {
40         queue<pair<int, int> > que;
41         que.push(pair<int, int>(_x, _y));
42         
43         while (!que.empty()) {
44             pair<int, int> blk = que.front();
45             que.pop();
46             int x = blk.first;
47             int y = blk.second;
48             if (y <= my && x <= mx && board[y][x] == oc) {
49                 board[y][x] = nc;
50                 if (x+1 <= mx && board[y][x+1] == oc) que.push(pair<int, int>(x+1, y));
51                 if (x-1 >= 0 && board[y][x-1] == oc) que.push(pair<int, int>(x-1, y));
52                 if (y+1 <= my && board[y+1][x] == oc) que.push(pair<int, int>(x, y+1));
53                 if (y-1 >= 0 && board[y-1][x] == oc) que.push(pair<int, int>(x, y-1));
54             }
55         }
56     }
57 };