|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +/** |
| 6 | + * Created by fishercoder1534 on 9/30/16. |
| 7 | + */ |
| 8 | +publicclassSurroundedRegionsBFS { |
| 9 | +/**I won't call this problem hard, it's just confusing, you'll definitely want to clarify what the problem means before coding. |
| 10 | + * This problem eactually means: |
| 11 | + * any grid that is 'O' but on the four edges, will never be marked to 'X'; |
| 12 | + * furthermore, any grid that is 'O' and that is connected with the above type of 'O' will never be marked to 'X' as well; |
| 13 | + * only all other nodes that has any one direct neighbor that is an 'X' will be marked to 'X'.*/ |
| 14 | + |
| 15 | + |
| 16 | +int[]dirs =newint[]{0,1,0,-1,0}; |
| 17 | + |
| 18 | +publicvoidsolve(char[][]board) { |
| 19 | +if(board ==null ||board.length ==0 ||board[0].length ==0)return; |
| 20 | +intm =board.length,n =board[0].length; |
| 21 | +Queue<int[]>queue =newLinkedList(); |
| 22 | +//check first row and last row and mark all those '0' on these two rows to be '+' to let them be different from other 'O', at the same time, we put them into the queue to get ready for a BFS to mark all those adjacent 'O' nodes to '+' as well |
| 23 | +for(intj =0;j <n;j++){ |
| 24 | +if(board[0][j] =='O') { |
| 25 | +board[0][j] ='+'; |
| 26 | +queue.offer(newint[]{0,j}); |
| 27 | + |
| 28 | + } |
| 29 | +if(board[m-1][j] =='O') { |
| 30 | +board[m-1][j] ='+'; |
| 31 | +queue.offer(newint[]{m-1,j}); |
| 32 | + } |
| 33 | + } |
| 34 | + |
| 35 | +//check first column and last column too |
| 36 | +for(inti =0;i <m;i++){ |
| 37 | +if(board[i][0] =='O') { |
| 38 | +board[i][0] ='+'; |
| 39 | +queue.offer(newint[]{i,0}); |
| 40 | + } |
| 41 | +if(board[i][n-1] =='O') { |
| 42 | +board[i][n-1] ='+'; |
| 43 | +queue.offer(newint[]{i,n-1}); |
| 44 | + } |
| 45 | + } |
| 46 | + |
| 47 | +while(!queue.isEmpty()){ |
| 48 | +int[]curr =queue.poll(); |
| 49 | +for(inti =0;i <4;i++){ |
| 50 | +intx =curr[0]+dirs[i]; |
| 51 | +inty =curr[1]+dirs[i+1]; |
| 52 | +if(x >=0 &&x <m &&y >=0 &&y <n &&board[x][y] =='O'){ |
| 53 | +board[x][y] ='+'; |
| 54 | +queue.offer(newint[]{x,y}); |
| 55 | + } |
| 56 | + } |
| 57 | + } |
| 58 | + |
| 59 | +//now we can safely mark all other 'O' to 'X', also remember to put those '+' back to 'O' |
| 60 | +for(inti =0;i <m;i++){ |
| 61 | +for(intj =0;j <n;j++){ |
| 62 | +if(board[i][j] =='O')board[i][j] ='X'; |
| 63 | +elseif(board[i][j] =='+')board[i][j] ='O'; |
| 64 | + } |
| 65 | + } |
| 66 | + } |
| 67 | + |
| 68 | +} |