【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 X

X O O X

X X O X

X O X X

　　After running your function, the board should be:

X X X X

X X X X

X X X X

X O X X

题目大意

　　一个二维网格。包括’X’与’O’。将所以被X包围的O区域用X替代，返回替代后后结果。

解题思路

　　採用广度优先遍历的方式。（也能够採用尝试深度优先的方式（会有栈溢出））,标记出全部的被包围的点，剩下的就是不被包围的点

代码实现

算法实现类

import java.util.LinkedList;

import java.util.List;

public class Solution {

    ////////////////////////////////////////////////////////////////////////////////////////////////

    // 以下採用广度度优先遍历的方式，找出全部的【不】被包围的点

    ////////////////////////////////////////////////////////////////////////////////////////////////

    public void solve(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++) {

                // 假设未被訪问过，有两种可能，第一是X点，第二是O点。O点一定是被X包围的

                // 此时将未訪问过的点设置为X是正确的

                if (!visited[i][j]) {

                    board[i][j] = 'X';

                }

            }

        }

    }

    /**

     * 深度优先，找不被包围的点

     *

     * @param board   二维网格

     * @param visited 訪问标记数组

     * @param round   广度优先搜索时外围一圈的元素

     */

    public void bfs(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));

            }

        }

    }

    ////////////////////////////////////////////////////////////////////////////////////////////////

    // 以下採用广度度优先遍历的方式，找出全部的被包围的点，而且标记会超时

    ////////////////////////////////////////////////////////////////////////////////////////////////

    public void solve2(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';

    }

    /**

     * 坐标对象

     */

    public static class Coordinate {

        private int x;

        private int y;

        public Coordinate() {

        }

        public Coordinate(int x, int y) {

            this.x = x;

            this.y = y;

        }

        @Override

        public String toString() {

            return "(" + x + ", " + y + ")";

        }

    }

}

评測结果

　　点击图片，鼠标不释放。拖动一段位置，释放后在新的窗体中查看完整图片。

特别说明

欢迎转载。转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47678211】