包围区域

import java.util.*;
public class Solution {
    public void solve(char[][] board) {
        if(board==null || board.length==0) return;
        for(int i=0,j=0;j<board[0].length;j++){
            if(board[i][j]=='O') solve(i,j,board);
        }
        for(int i=board.length-1,j=0;j<board[0].length;j++){
            if(board[i][j]=='O') solve(i,j,board);
        }
        for(int i=1,j=0;i<board.length-1;i++){
            if(board[i][j]=='O') solve(i,j,board);
        }
        for(int i=1,j=board[0].length-1;i<board.length-1;i++){
            if(board[i][j]=='O') solve(i,j,board);
        }
        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';
            }
        }
    }
    static boolean solve(int i,int j,char[][] board){
        if(board[i][j]=='X' || board[i][j]=='*') return true;
        board[i][j]='*';
        if(i-1>=0) solve(i-1,j,board);
        if(i+1<board.length) solve(i+1,j,board);
        if(j-1>=0) solve(i,j-1,board);
        if(j+1<board[0].length)solve(i,j+1,board);
         return true;
    }

public class Solution {
    
    public void solve(char[][] board) {
        int len = board.length;
        if (len == 0)
            return;
        int width = board[0].length;
        if (width == 0)
            return;
        
        int[][] experiment = new int[len][width];
        for(int i = 0; i < len; i++)
            for (int j = 0; j < width; j++)
            {
                if ((board[i][j] == 'O') &&(experiment[i][j] == 0))
                {
                    if (findway(board,len,width,i,j,experiment) == false)
                    {
                        for (int k = 0; k < len; k++)
                            for (int l =0 ;l < width;l++)
                            {
                                if ((board[k][l] == 'O')&&(experiment[k][l] == 1))
                                {
                                    board[k][l] = 'X';
                                    experiment[k][l] = 2;
                                }
                            }
                    }
                    else 
                    {
                        for (int k = 0; k < len; k++)
                            for (int l =0 ; l < width; l++)
                            {
                                if ((board[k][l] == 'O')&&(experiment[k][l] == 1))
                                {
                                    experiment[k][l] = 2;
                                }
                            }
                    }
                }
            }

        return;
    }
    
    public boolean findway(char[][] board, int len, int width, int x, int y, int[][] experiment)
    {
        if(experiment[x][y] == 0)
        {
            experiment[x][y] = 1;
            if (x+1 == len)
                return true;
            if (x-1 == -1)
                return true;
            if (y+1 == width)
                return true;
            if (y-1 == -1)
                return true;
            
            if ((board[x+1][y] == 'O')&&(experiment[x+1][y] == 0))
            {
                if (findway(board,len,width,x+1,y,experiment) == true)
                    return true;
            }
            if ((board[x-1][y] == 'O')&&(experiment[x-1][y] == 0))
            {
                if (findway(board,len,width,x-1,y,experiment) == true)
                    return true;
            }
            if ((board[x][y+1] == 'O')&&(experiment[x][y+1] == 0))
            {
                                // 问题就在这个地方，只要把里面的y+1改成y就能过第一个点，也是醉了
                if (findway(board,len,width,x,y+1,experiment) == true)
                    return true;
            }
            if ((board[x][y-1] == 'O')&&(experiment[x][y-1] == 0))
            {
                if (findway(board,len,width,x,y-1,experiment) == true)
                    return true;
            }
            
            return false;
        }
        else
            return false;
    }
    

}

class Solution {
    public void solve(char[][] board) {
        int row=board.length;
        if(row==0) return ;
        int col=board[0].length;
        for(int i=0;i<col;i++) {
        	if(board[0][i]=='o') 
        		sortcap(0,i,row,col,board);
        	if(board[row-1][i]=='o') 
        		sortcap(row-1,i,row,col,board);
        }
        for(int i=1;i<row-1;i++) {
        	if(board[i][0]=='o') 
        		sortcap(i,0,row,col,board);
        	if(board[i][col-1]=='o') 
        		sortcap(i,col-1,row,col,board);	        	
        }
        for(int i=0;i<row;i++) {
        	for(int j=0;j<col;j++) {
        		if(board[i][j]=='o')
        			board[i][j]='x';
        	}
        }
        for(int i=0;i<row;i++) {
        	for(int j=0;j<col;j++) {
        		if(board[i][j]=='*')
        			board[i][j]='o';
        	}
        }
    }
    public void sortcap(int x,int y,int row,int col,char[][] board) {
    	board[x][y]='*';
    	if(x+1<row&&board[x+1][y]=='o')
    		sortcap(x+1,y,row,col,board);
    	if(x-1>=0&&board[x-1][y]=='o')
    		sortcap(x-1,y,row,col,board);
    	if(y+1<col&&board[x][y+1]=='o')
    		sortcap(x,y+1,row,col,board);
    	if(y-1>=0&&board[x][y-1]=='o')
    		sortcap(x,y-1,row,col,board);
    }
 }
/*
不能ac，本地正常
*/

import java.util.*;

public class Solution {
    static int rowLen;
    static int colLen;
    
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        rowLen = board.length;
        colLen = board[0].length;
        HashSet<Point> pointSet = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    pointSet.add(new Point(i, j));
                }
            }
        }
        while (!pointSet.isEmpty()) {
            Point point = null;
            for (Point apoint :
                    pointSet) {
                point = apoint;
                break;
            }
            Queue<Point> queue = new LinkedList<>();
            queue.offer(point);
            pointSet.remove(point);
            ArrayList<Point> arrayList = new ArrayList<>();//保存一个连通区域的所有O点
            boolean isToReplace = true;//初始化是否待修改该区域为true
            while (!queue.isEmpty()) {
                Point point1 = queue.poll();
                arrayList.add(point1);
                for (Point point2 :
                        point1.getLinkedPoints()) {
//                Point point2 = point1.upPoint();
                    if (point2.isValid()) {
                        if (pointSet.contains(point2)) {
                            queue.offer(point2);
                            pointSet.remove(point2);

                        }
                    } else {
                        isToReplace = false;//说明该区域无需修改
                    }

                }
            }
            //区域已生成，现在进行修改
            if (isToReplace) {
                for (Point point3 :
                        arrayList) {
                    board[point3.x][point3.y] = 'X';
                }
            }
        }
    }
    
    static class Point {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int x;
        int y;

        boolean isValid() {
            return x >= 0 && x < rowLen && y >= 0 && y < colLen;
        }

        Set<Point> getLinkedPoints() {
            HashSet<Point> hashSet = new HashSet<>();
            hashSet.add(upPoint());
            hashSet.add(downPoint());
            hashSet.add(leftPoint());
            hashSet.add(rightPoint());
            return hashSet;
        }

        Point upPoint() {
            return new Point(x, y - 1);
        }

        Point downPoint() {
            return new Point(x, y + 1);
        }

        Point leftPoint() {
            return new Point(x - 1, y);
        }

        Point rightPoint() {
            return new Point(x + 1, y);
        }
        
        @Override
        public int hashCode() {
            return x + y;//super.hashCode()//x * (y + 1)
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Point) {
                Point point = (Point) obj;
                return x == point.x && y == point.y;
            }
            return super.equals(obj);
        }
    }
} 

import java.util.Arrays;

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length < 2 || board[0].length < 2)
            return;
        int row = board.length;
        int col = board[0].length;

        //检查第一行和最后一行是否有'O'
        for (int i = 0; i < col; i++) {
            if (board[0][i] == 'O') {
                check(board,0,i);
            }

            if (board[row-1][i] == 'O') {
                check(board, row-1, i);
            }
        }

        //检查第一列和最后一列是否有'O'
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O'){
                check(board, i, 0);
            }

            if(board[i][col-1] == 'O') {
                check(board, i, col-1);
            }
        }
        //遍历数组，将O改为X
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        //遍历数组，将*改为O
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '*')
                    board[i][j] = 'O';
            }
        }
    }

    /**
     * 检查与i,j相连的O，将其设置为*
     * @param board
     * @param i
     * @param j
     */
    private void check(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length)
            return;
        if (board[i][j] == 'O') {
            board[i][j] = '*';
        }
        if (i > 1 && board[i-1][j] == 'O')
            check(board, i-1, j);
        if (j > 1 && board[i][j-1] == 'O')
            check(board, i, j-1);
        if (i < board.length-1 && board[i+1][j] == 'O')
            check(board, i+1, j);
        if (j < board[0].length-1 && board[i][j+1]=='O')
            check(board, i, j+1);
    }
}

import java.util.*;
public class Solution {
        char [][]board;
        int row;
        int col;
        Queue<Integer> queue=new LinkedList<Integer>();
        
        public void solve(char [][]board){
            this.board=board;
            row=board.length;
            if(row<3)
                return;
            col=board[0].length;
            if(col<3)
                return;
            //traverse first column and last column
            for(int i=0;i<row;i++){
                bfs(i,0);
                bfs(i,col-1);
            }
            //traverse first row and last row
            for(int j=0;j<col;j++){
                bfs(0,j);
                bfs(row-1,j);
            }
            //change 'O' to 'X',restore '#' to 'O'
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    if(board[i][j]=='O')
                        board[i][j]='X';
                    else if(board[i][j]=='#')
                        board[i][j]='O';
                }
            }
        }
    public void bfs(int i,int j){
        fill(i,j);
        while(!queue.isEmpty()){
            int pos=queue.poll();
            int x=pos/col;
            int y=pos%col;
            
            fill(x-1,y);
            fill(x+1,y);
            fill(x,y-1);
            fill(x,y+1);
        }
    }
    public void fill(int i,int j){
        if(i<0 || j<0 || i>row-1 || j>col-1)
            return;
        if(board[i][j] !='O')
            return;
        queue.offer(i*col+j);
        board[i][j]='#';
    }
}

//感谢一楼的思路，自己再理解一下，就是O能找到出口的问题，然后从出口处的O反过来去找
//出来的路径。
public class Solution {
	public void DFS(char[][] board, int row, int col)
	{
		if(row < 0 || row>(board.length - 1) || col < 0 || col >(board[0].length -1) ) return ;
		if(board[row][col] == 'O') 
			{
				board[row][col] = '*';
				DFS(board, row-1,col);
				DFS(board,row+1,col);
				DFS(board,row,col-1);
				DFS(board,row,col+1);
			}
	}
    public void solve(char[][] board) {
        if(board.length <= 0) return;
        int row = board.length;
        int col = board[0].length;
        for(int i = 0 ; i != row ; i++) {
            DFS(board,i,col-1);
            DFS(board,i,0);
         } 
        for(int i = 0 ; i != col ;i++) 
       { 
         DFS(board,0,i); 
         DFS(board,row-1,i);
        }
        for(int i = 0 ; i != row ; i++)
          for(int j = 0 ; j != col ; j++)
              { if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '*') board[i][j] = 'O'; 
              }
     }
 }

public class Solution {
    public int[][] f;
    public void solve(char[][] board) {
        if(board==null || board.length==0)return;
        f = new int[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(i==0 || i==board.length-1 || j==0 || j==board[0].length-1)
                    setter(board,i,j);
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(f[i][j]==1)
                    board[i][j] = 'O';
                else
                    board[i][j] = 'X';
            }
        }       
    }
    public void setter(char[][] board, int i, int j){
        if(i<0 || i>=board.length || j<0 || j>=board[0].length)return ;
        if(board[i][j] != 'O' || f[i][j]==1)return;
        
        f[i][j] = 1;
        setter(board,i+1,j);
        setter(board,i-1,j);
        setter(board,i,j+1);
        setter(board,i,j-1);
    }
}

import java.util.Stack;
import java.util.LinkedList;
public class Solution {
	public static void solve(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0)
			return;
		int xLen = board.length;
		int yLen = board[0].length;
		for (int i = 0; i < xLen; ++i) {
			if (board[i][0] == 'O') {
				bfs(i, 0, board, 'O', '?');
			}
			if (board[i][yLen - 1] == 'O') {
				bfs(i, yLen - 1, board, 'O', '?');
			}
		}
		for (int j = 0; j < yLen; ++j) {
			if (board[0][j] == 'O') {
				bfs(0, j, board, 'O', '?');
			}
			if (board[xLen - 1][j] == 'O') {
				bfs(xLen - 1, j, board, 'O', '?');
			}
		}
		for (int i = 0; i < xLen; ++i) {
			for (int j = 0; j < yLen; ++j) {
				if (board[i][j] == 'O') {
					board[i][j] = 'X';
				}
				if (board[i][j] == '?') {
					board[i][j] = 'O';
				}
			}
		}
	}

	public static void dfs(int x, int y, char[][] board, char findChar, char replaceChar) {
		int xLen = board.length;
		int yLen = board[0].length;
		if (x < 0 || x >= xLen || y < 0 || y >= yLen)
			return;
		if (board[x][y] == findChar) {
			board[x][y] = replaceChar;
			dfs(x, y - 1, board, findChar, replaceChar);
			dfs(x, y + 1, board, findChar, replaceChar);
			dfs(x + 1, y, board, findChar, replaceChar);
			dfs(x - 1, y, board, findChar, replaceChar);
		}
	}

	public static void bfs(int x, int y, char[][] board, char findChar, char replaceChar) {
		int xLen = board.length;
		int yLen = board[0].length;
		if (x < 0 || x >= xLen || y < 0 || y >= yLen)
			return;
		LinkedList<int[]> queue = new LinkedList<int[]>();
		if (board[x][y] == findChar) {
			board[x][y] = replaceChar;
			queue.add(new int[] { x, y });
		}
		while (!queue.isEmpty()) {
			int[] temp = queue.poll();
			int tempX = temp[0];
			int tempY = temp[1];
			if (tempX - 1 >= 0 && board[tempX - 1][tempY] == findChar) {
				board[tempX - 1][tempY] = replaceChar;
				queue.add(new int[] { tempX - 1, tempY });
			}
			if (tempX + 1 < xLen && board[tempX + 1][tempY] == findChar) {
				board[tempX + 1][tempY] = replaceChar;
				queue.add(new int[] { tempX + 1, tempY });
			}
			if (tempY - 1 >= 0 && board[tempX][tempY - 1] == findChar) {
				board[tempX][tempY - 1] = replaceChar;
				queue.add(new int[] { tempX, tempY - 1 });
			}
			if (tempY + 1 < yLen && board[tempX][tempY + 1] == findChar) {
				board[tempX][tempY + 1] = replaceChar;
				queue.add(new int[] { tempX, tempY + 1 });
			}
		}
	}

	public static void dfs_stack(int x, int y, char[][] board, char findChar, char replaceChar) {
		int xLen = board.length;
		int yLen = board[0].length;
		if (x < 0 || x >= xLen || y < 0 || y >= yLen)
			return;
		Stack<int[]> stack = new Stack<int[]>();
		if (board[x][y] == findChar) {
			stack.add(new int[] { x, y });
		}
		while (!stack.isEmpty()) {
			int[] temp = stack.pop();
			int tempX = temp[0];
			int tempY = temp[1];
			board[tempX][tempY] = replaceChar;
			if (tempX - 1 >= 0 && board[tempX - 1][tempY] == findChar) {
				stack.push(new int[] { tempX - 1, tempY });
			}
			if (tempX + 1 < xLen && board[tempX + 1][tempY] == findChar) {
				stack.push(new int[] { tempX + 1, tempY });
			}
			if (tempY - 1 >= 0 && board[tempX][tempY - 1] == findChar) {
				stack.push(new int[] { tempX, tempY - 1 });
			}
			if (tempY + 1 < yLen && board[tempX][tempY + 1] == findChar) {
				stack.push(new int[] { tempX, tempY + 1 });
			}
		}
	}


}

public class SurroundedRegions {

	//本题使用广度优先搜索算法，类似迷宫题，可以参考http://www.2cto.com/kf/201605/509249.html和http://www.acmerblog.com/leetcode-surrounded-regions-6171.html
	public static void solve(char[][] board) {

		if (board == null || board.length == 0)
			return;
		boolean[][] visited = new boolean[board.length][board[0].length];
		LinkedList<Integer> queue = new LinkedList<>();
		int dir[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };// 定义四个方向
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == 'O' && !visited[i][j]) {
					boolean surrounded = true;
					List<Integer> visitedPoint = new ArrayList<>();//记录访问过的点，用来把‘O’涂成‘X’
					queue.offer(i * board[0].length + j);
					visited[i][j] = true;
					while (!queue.isEmpty()) {
						int point = queue.poll();
						visitedPoint.add(point);
						int x = point / board[0].length;
						int y = point % board[0].length;
						for (int k = 0; k < 4; k++) {//控制搜索的四個方向
							int nextX = x + dir[k][0];
							int nextY = y + dir[k][1];
							if (nextX >= 0 && nextX < board.length && nextY >= 0 && nextY < board[0].length) {
								if (board[nextX][nextY] == 'O' && !visited[nextX][nextY]) {
									queue.offer(nextX * board[0].length + nextY);
									visited[nextX][nextY] = true;
								}

							} else {//如果下个点超出数组范围，说明现在的点是边缘，所以必定没有被包围
								surrounded = false;
							}
						}

					}
					if (surrounded) {
						for (int p : visitedPoint) {
							board[p / board[0].length][p % board[0].length] = 'X';
						}
					}
				}
			}
		}
	}

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

 public void solve(char[][] board) {