- Surrounded Regions
Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.
A region is captured by flipping all 'O’s into 'X’s in that surrounded region.
Example 1:
Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
Explanation: Notice that an ‘O’ should not be flipped if:
- It is on the border, or
- It is adjacent to an ‘O’ that should not be flipped.
The bottom ‘O’ is on the border, so it is not flipped.
The other three ‘O’ form a surrounded region, so they are flipped.
思路：考虑到目标是“把所有内部被X围住的O转成X”，把所有外围（还有与外围相连的）的O 转成 F （ 也可以是其他别的字符）；
然后，遍历整个矩阵，把此时所有O转成X，把所有F恢复成O.
public void solve(char[][] ma){int n = ma.length;int m = ma[0].length;for(int i=0;i<n;i++){if(ma[i][0]=='O'){free(ma,i,0);}if(ma[i][m-1]=='O'){free(ma,i,m-1);}}for(int j=1;j<m-1;j++){if(ma[0][j]=='O'){free(ma,0,j);}if(ma[n-1][j]=='O'){free(ma,n-1,j);}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(ma[i][j]=='O'){ma[i][j]='X';}if(ma[i][j]=='F'){ma[i][j]='O';}}}}public void free(char[][] ma, int i, int j){if(i<0||i>=ma.length||j<0||j>=ma[0].length||ma[i][j]!='O'){return;}ma[i][j]='F';free(ma,i-1,j);free(ma,i,j-1);free(ma,i+1,j);free(ma,i,j+1);}
