【130-Surrounded Regions（环绕区域）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region. For example,
X X X XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX O X X题目大意
一个二维网格，包含’X’与’O’，将所以被X包围的O区域用X替代，返回替代后后结果。
解题思路
采用广度优先遍历的方式，（也可以采用尝试深度优先的方式（会有栈溢出））,标记出所有的被包围的点，剩下的就是不被包围的点
代码实现
算法实现类
import java.util.LinkedList;import java.util.List;public class Solution {(char[][] board) {// 参数校验if (board == null || board.length < 1 || board[0].length < 1) {return;}boolean[][] visited = new boolean[board.length][board[0].length];// 广度优先搜索时外围一圈的元素List<Coordinate> round = new LinkedList<>();// 处理顶部行for (int col = 0; col < board[0].length; col++) {// 顶部行，并且点是O并且点未被访问过if (!visited[0][col] && board[0][col] == ‘O’) {round.clear();round.add(new Coordinate(0, col));bfs(board, visited, round);}}// 处理底部行for (int col = 0; col < board[0].length; col++) {// 顶部行，并且点是O并且点未被访问过if (!visited[board.length – 1][col] && board[board.length – 1][col] == ‘O’) {round.clear();round.add(new Coordinate(board.length – 1, col));bfs(board, visited, round);}}// 处理左边列for (int row = 1; row < board.length – 1; row++) {// 顶部行，，并且点是O并且点未被访问过if (!visited[row][0] && board[row][0] == ‘O’) {round.clear();round.add(new Coordinate(row, 0));bfs(board, visited, round);}}// 处理右边列for (int row = 1; row < board.length – 1; row++) {// 顶部行，并且点是O并且点未被访问过if (!visited[row][board[0].length – 1] && board[row][board[0].length – 1] == ‘O’) {round.clear();round.add(new Coordinate(row, board[0].length – 1));bfs(board, visited, round);}}// 标记网格for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {(!visited[i][j]) {board[i][j] = ‘X’;}}}}/*** 深度优先，找不被包围的点** @param board 二维网格* @param visited 访问标记数组* @param round 广度优先搜索时外围一圈的元素*/(char[][] board, boolean[][] visited, List<Coordinate> round) {Coordinate c;while (round.size() > 0) {c = round.remove(0);if (c.x >= 0 && c.x < board.length && c.y >= 0 && c.y < board[0].length && board[c.x][c.y] == ‘O’ && !visited[c.x][c.y]) {visited[c.x][c.y] = true;round.add(new Coordinate(c.x – 1, c.y));round.add(new Coordinate(c.x, c.y + 1));round.add(new Coordinate(c.x + 1, c.y));round.add(new Coordinate(c.x, c.y – 1));}}}(char[][] board) {// 参数校验if (board == null || board.length < 1 || board[0].length < 1) {return;}boolean[][] visited = new boolean[board.length][board[0].length];// 广度优先搜索时外围一圈的元素List<Coordinate> round = new LinkedList<>();// 广度优先搜索进的所有元素List<Coordinate> all = new LinkedList<>();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (!visited[i][j] && board[i][j] == ‘O’) {// 广度优先搜索第一圈的元素round.add(new Coordinate(i, j));boolean result = bfs(board, visited, round, all);// 一次搜索的所有O都在网格内，并且不在边界上if (result) {// 设置标记for (Coordinate c : all) {board[c.x][c.y] = ‘X’;}}// 清空元素round.clear();all.clear();}}}}/*** 广度优先遍历** @param board 二维网格* @param visited 访问标记数组* @param round 广度优先搜索时外围一圈的元素* @param all广度优先搜索进的所有元素* @return true点是O，点在网格内，并且不在边界上，如果点是X，总返回true*/public boolean bfs(char[][] board, boolean[][] visited, List<Coordinate> round, List<Coordinate> all) {boolean result = true;int size = round.size();Coordinate c;while (size > 0) {size–;// 取队首元素c = round.remove(0);// 添加到遍历记录元素集合中all.add(c);// 标记已经被访问过了visited[c.x][c.y] = true;// 判断c是否是O内点result &= isInner(board, c.x, c.y);// c的上面一个点是否是O，并且没有访问过，满足就添加到round队列中if (isO(board, c.x – 1, c.y) && !visited[c.x – 1][c.y]) {round.add(new Coordinate(c.x – 1, c.y));}// c的右面一个点是否是O，并且没有访问过，满足就添加到round队列中if (isO(board, c.x, c.y + 1) && !visited[c.x][c.y + 1]) {round.add(new Coordinate(c.x, c.y + 1));}// c的下面一个点是否是O，并且没有访问过，满足就添加到round队列中if (isO(board, c.x + 1, c.y) && !visited[c.x + 1][c.y]) {round.add(new Coordinate(c.x + 1, c.y));}// c的左面一个点是否是O，并且没有访问过，满足就添加到round队列中if (isO(board, c.x, c.y – 1) && !visited[c.x][c.y – 1]) {round.add(new Coordinate(c.x, c.y – 1));}}if (round.size() > 0) {return bfs(board, visited, round, all) && result;} else {return result;}}/*** 判断点在二维风格内部，并且不在边界上** @param board 二维网格* @param x横坐标* @param y纵坐标* @return true是*/public boolean isInner(char[][] board, int x, int y) {return x > 0 && x < board.length – 1 && y > 0 && y < board[0].length – 1;}/*** 判断点是否是O** @param board 二维网格* @param x横坐标* @param y纵坐标* @return true是*/public boolean isO(char[][] board, int x, int y) {return x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == ‘O’;}/*** 坐标对象*/Coordinate {private int x;private int y;public Coordinate() {}public Coordinate(int x, int y) {this.x = x;this.y = y;}@Overridepublic String toString() {return “(” + x + “, ” + y + “)”;}}}评测结果
点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
多看书，看好书。
