https://leetcode.com/problems/surrounded-regions/

类似BFS的思想,从2D数组的边出发,每一个和边上=O相邻的且本身也为O的元素记录下来,这些元素不需要换成X

import java.util.HashSet;
import java.util.Set;

public class SurroundedRegions {

    public static void solve(char[][] board) {
        Set<String> locationSet = new HashSet();

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(j == 0 || j == board[i].length - 1
                        || i == 0 || i == board.length - 1){
                    //'O' on the border or vertex
                    if(board[i][j] == 'O'){
                        adjacencyOPoint(i, j, board, locationSet);
                    }
                }
            }
        }

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(board[i][j] == 'O'){
                    String location = i + "," + j;
                    if(!locationSet.contains(location)){
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }

    private static void adjacencyOPoint(int i, int j, char[][] board, Set<String> locationSet){
        if(locationSet.contains(i + "," + j)){
            return;
        }
        locationSet.add(i + "," + j);
        if(i - 1 > 0 && board[i - 1][j] == 'O'){
            adjacencyOPoint(i - 1, j, board, locationSet);
        }
        if(i + 1 < board.length && board[i + 1][j] == 'O'){
            adjacencyOPoint(i + 1, j, board, locationSet);
        }
        if(j - 1 > 0 && board[i][j - 1] == 'O'){
            adjacencyOPoint(i, j - 1, board, locationSet);
        }
        if(j + 1 < board[i].length && board[i][j + 1] == 'O'){
            adjacencyOPoint(i, j + 1, board, locationSet);
        }
        return;
    }

    public static void main(String args[]){
        char[][] board = new char[][]
                {
                        {'O','O','O'},
                        {'O','O','O'},
                        {'O','O','O'},
                };
        solve(board);
    }

}