|
| 1 | +/* |
| 2 | +Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. |
| 3 | +Time: O(n^2) |
| 4 | +Space: O(1) |
| 5 | +*/ |
| 6 | + |
| 7 | + |
| 8 | +voiddfsModifyBorder(char**board,intn,intm,inti,intj) { |
| 9 | +if (board[i][j]=='X') |
| 10 | +return; |
| 11 | +board[i][j]='T'; |
| 12 | +if (i>0&&board[i-1][j]=='O') |
| 13 | +dfsModifyBorder(board,n,m,i-1,j); |
| 14 | +if (j>0&&board[i][j-1]=='O') |
| 15 | +dfsModifyBorder(board,n,m,i,j-1); |
| 16 | +if (i<(n-1)&&board[i+1][j]=='O') |
| 17 | +dfsModifyBorder(board,n,m,i+1,j); |
| 18 | +if (j<(m-1)&&board[i][j+1]=='O') |
| 19 | +dfsModifyBorder(board,n,m,i,j+1); |
| 20 | +} |
| 21 | + |
| 22 | +voidreModifyBorder(char**board,intn,intm) { |
| 23 | +inti,j; |
| 24 | +for (i=0;i<n;i++){ |
| 25 | +for (j=0;j<m;j++){ |
| 26 | +if (board[i][j]=='O') |
| 27 | +board[i][j]='X'; |
| 28 | +elseif (board[i][j]=='T') |
| 29 | +board[i][j]='O'; |
| 30 | + } |
| 31 | + } |
| 32 | +} |
| 33 | + |
| 34 | +voidsolve(char**board,intboardSize,int*boardColSize){ |
| 35 | +inti,j; |
| 36 | +intm= (*boardColSize); |
| 37 | +intn1=boardSize-1; |
| 38 | +intm1=m-1; |
| 39 | +for (i=1;i<n1;i++) { |
| 40 | +dfsModifyBorder(board,boardSize,m,i,0); |
| 41 | +dfsModifyBorder(board,boardSize,m,i,m1); |
| 42 | + } |
| 43 | +for (j=0;j<m;j++) { |
| 44 | +dfsModifyBorder(board,boardSize,m,0,j); |
| 45 | +dfsModifyBorder(board,boardSize,m,n1,j); |
| 46 | + } |
| 47 | +reModifyBorder(board,boardSize,m); |
| 48 | +} |