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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
public class SurroundedRegions { Queue<Pair> queue = new LinkedList<Pair>(); public void solve(char[][] board) { if (board == null || board.length < 3 || board[0] == null || board[0].length < 3) { return; } for (int i = 0; i < board.length; i++) { if (board[i][0] == 'O') { helper(board, i, 0); } if (board[i][board[0].length - 1] == 'O') { helper(board, i, board[0].length - 1); } } for (int i = 0; i < board[0].length; i++) { if (board[0][i] == 'O') { helper(board, 0, i); } if (board[board.length - 1][i] == 'O') { helper(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'; } if (board[i][j] == '#') { board[i][j] = 'O'; } } } } private void helper(char[][] board, int i, int j) { search(board, i, j); while (!queue.isEmpty()) { Pair p = queue.poll(); search(board, p.x + 1, p.y); search(board, p.x - 1, p.y); search(board, p.x, p.y + 1); search(board, p.x, p.y - 1); } } private void search(char[][] board, int i, int j) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') { return; } queue.add(new Pair(i, j)); board[i][j] = '#'; } static class Pair { Pair(int x, int y) { this.x = x; this.y = y; } int x, y; } }
|