EEPW论坛

Given a 2D board containing'X'and'O', capture all regions surrounded by'X'.

A region is captured by flipping all'O's into'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

1. class Solution  

2. {  

3. public:  

4.     void dfs(int row, int col, vector<vector<char>>&  board)  

5.     {  

6.         if (row<0 || row>=rows || col<0 || col>=cols)  

7.         {  

8.             return;  

9.         }  

10.   

11.         if (board[row][col]!='O')  

12.         {  

13.             return;  

14.         }  

15.         board[row][col] = '+';  

16.         dfs(row - 1, col, board); //up  

17.         dfs(row, col + 1, board); //right  

18.         dfs(row + 1, col, board); //down  

19.         dfs(row, col - 1, board); //left  

20.     }  

21.   

22.     void solve(vector<vector<char>>& board)  

23.     {  

24.         if (board.size()==0 || board[0].size()==0)  

25.         {  

26.             return;  

27.         }  

28.   

29.         rows = board.size();  

30.         cols = board.size();  

31.   

32.         for (int i=0; i<rows; i++)  

33.         {  

34.             dfs(i, 0, board);//第一列  

35.             dfs(i, cols-1, board);//最后一列  

36.         }  

37.   

38.         for (int j=0; j<cols; ++j)  

39.         {  

40.             dfs(0, j, board);//第一行  

41.             dfs(rows-1, j, board);//最后一行  

42.         }  

43.   

44.         for (int i=0; i<rows; i++)  

45.         {  

46.             for (int j=0; j<cols; j++)  

47.             {  

48.                 if (board[i][j]=='O')  

49.                 {  

50.                     board[i][j] = 'X';  

51.                 }  

52.                 else if (board[i][j]=='+')  

53.                 {  

54.                     board[i][j] = 'O';  

55.                 }  

56.             }  

57.         }  

58.     }  

59.   

60. private:  

61.     int rows;//总行号  

62.     int cols;//总列号  

63. };