题意：这道题是说一个O周围都是X那么这个O就得变成X。那么就可以发现四周这一圈如果有O肯定不能四周都被X包围，同时这个O也将会是潜在的内部的O的缺口。 思路：用BFS。对第一行和最后一行，第一列和最后一列进行遍历，若是X，则不作处理直接返回；若是O，则遍历其上下左右的元素，若是有O，则把相邻的O置为#；结束之后，遍历每一个元素，若为#，则说明之前的是O，把#置为O即可；若还是为O，则说明这个O是被X包围的，将其置为X即可；主要是一个广度遍历的思想。 代码：
package com.SurroundedRegions; import java.util.LinkedList; public class SurroundedRegions { public void fill(char[][] board , int i ,int j) { if(board[i][j] != 'O') return; board[i][j] = '#'; LinkedList<Integer> queue = new LinkedList<>(); int code = i*board[0].length+j; queue.add(code); while (!queue.isEmpty()) { code = queue.poll(); int row = code/board[0].length; int col = code%board[0].length; //当前元素的上面是否为O if(row >= 1 && board[row - 1][col] == 'O'){ queue.add((row-1)*board[0].length+col); board[row-1][col] = '#'; } //当前元素的下面是否为O if(row <= board.length - 2 && board[row + 1][col] == 'O'){ queue.add((row+1)*board[0].length+col); board[row+1][col] = '#'; } //当前元素的左面是否为O if(col >=1 && board[row][col-1] == 'O'){ queue.add(row*board[0].length+col-1); board[row][col-1] = '#'; } //当前元素的右面是否为O if(col <= board[0].length - 2 && board[row][col+1] == 'O'){ queue.add(row*board[0].length+col+1); board[row][col+1] = '#'; } } } public char[][] solve(char[][] board) { //填充第一行和最后一行 for(int i = 0 ; i < board[0].length ; i++){ fill(board , 0, i); fill(board, board.length-1, i); } //填充第一列和最后一列 for(int j = 0 ; j < board.length ; j++){ fill(board, j, 0); fill(board, j, board[0].length-1); } 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] == '#' ) board[i][j] = 'O'; } } return board; } public static void main(String[] args) { char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}}; char[][] temp = new SurroundedRegions().solve(board); for (char[] cs : temp) { for (char c : cs) { System.out.print(c+" "); } } } }