surrounded regions

Posted on |

leetCode130, like go game.

how to design the solution, at first it is naive to traverse with two for loops, then there will be too many if statement to specify, and not clear to seperate these if statements.

three ideas behind a sample solution.

using addtional status variable

in lower space the problem is difficult to analysis, then from a higher space, the problem is clear and easy. e.g. trakcing the O in the board, how to mark them ? keep O will not tell the marked ones and the original ones. so using M to mark these already traversed, it make the situation much more clear

starting from the critial domain

at first, no idea where is a good start point, but the trick point is at the boundary, only the cells at boundary with O will keep O; all the O not on the boundary either connect to the boundary Os or they will be Xs.

traversing with queue

if not queue, to detect these O cells need two for loops, then deal with these O cells again need another two for loops.

for loop is a global handling, while queue list is a local way, no need to take all cells in consideration, but only the cells in queue.

queue should be a good way to traverse whenever the operation is not deal with all the elements. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//extending from the boundary 'O', any extened will keep same statue
void process(int i, int j, vector<vector<char>>& board){
  int height = board.size();
  int width = board[0].size();
  std::pair<int, int> p;
  queue<std::pair<int, int>> Q ;
  Q.push(p(i,j));
  board[i][j] = 'm';
  while(!Q.empty()){
      p tmp = Q.front(); Q.pop();
      i=tmp.first;
      j=tmp.second;
      if(i!=0 && board[i-1][j] == 'O'){
        board[i-1][j] = 'm';
        Q.push(p[i-1][j]);
      }
      if(i!= width-1 && board[i+1][j]=='O')
      {
        board[i+1][j] = 'm';
        Q.push(p[i+1][j]);
      }
      if(j!=0 && board[i][j-1]=='0')
      {
        board[i][j-1]='m';
        Q.push(p[i][j-1]);
      }
      if(j!=height-1 && board[i][j+1]=='O')
      {
        board[i][j+1] = 'm';
        Q.push(p[i][j+1]);
      }
  }
}
void sol(vector<vector<char>>& board){
  int height = board.size();
  int width = board[0].size();
//tracking the boundary 'o' and mark them as 'm'
  for(int i=0; i<width; i++){
    if(board[i][0] == 'O'){ //bottom boundary
      board[i][0] = 'm' ;
      process(i, 0, board);
    }
    if(board[i][height-1] == 'O')
    {
        board[i][height-1] = 'm' ;
        process(i, height-1, board);
      }
  }
  for(int j=0; j<height; j++){
    if(board[0][j] == 'O'){
      board[0][j] = 'm';
      process(0, j, board);
    }
     if(board[width-1][j] == 'O')
    {
        board[width-1][j] = 'm' ;
        process(width-1, j, board);
      }
  }
  for(int i=0; i<width; i++)
    for(int j=0; j<height; j++){
      if(board[i][j] == 'O')
        board[i][j] = 'X';
      if(board[i][j] == 'm')
        board[i][j] = 'O';
    }
  }
}