[leetcode]Surrounded Regions

这题leetcode设的memory好紧... 最后把recursion换成iterative做才过.. 还有BFS忘了track visited loop 搞了很久 

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

public class Solution { public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) return; for (int i = 0; i < board.length; i++){ if (board[i][0] == 'O') filpEdgeRegionToOne(board, i, 0); if (board[i][board[0].length-1] == 'O') filpEdgeRegionToOne(board, i, board[0].length-1); } for (int i = 0; i < board[0].length; i++){ if (board[0][i] == 'O') filpEdgeRegionToOne(board, 0, i); if (board[board.length-1][i] == 'O') filpEdgeRegionToOne(board, board.length-1, i); } for (int i = 0; i < board.length; i++){ for (int j = 0; j < board[0].length; j++){ if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == '1') board[i][j] = 'O'; } } } void filpEdgeRegionToOne(char[][]board, int i, int j){ int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}}; Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[]{i,j}); while (!queue.isEmpty()){ int []location = queue.poll(); if (board[location[0]][location[1]] == 'O'){ board[location[0]][location[1]] = '1'; for (int k = 0; k < dirs.length; k++){ int x = location[0]+dirs[k][0]; int y = location[1]+dirs[k][1]; if (checkValid(board, x, y)) queue.add(new int[]{x,y}); } } } } boolean checkValid(char[][] board, int i, int j){ return !(i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] == 'X' || board[i][j] == '1'); } }