搜索

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3
链接：https://leetcode-cn.com/problems/number-of-islands
 

public class NumIslands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int num = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    num++;
                    search(grid, i, j, row, col);
                }
            }
        }
        return num;
    }
    private void search(char[][] grid, int x, int y, int row, int col) {
        if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] != '1') {
            return;
        }
        grid[x][y] = '2';
        search(grid, x - 1, y, row, col);
        search(grid, x + 1, y, row, col);
        search(grid, x, y - 1, row, col);
        search(grid, x, y + 1, row, col);
    }
}

==============================================================================

N皇后问题

public class Nqueue {
    private boolean[] col;
    private boolean[] dia1;
    private boolean[] dia2;
    private ArrayList<List<String>> res = new ArrayList<>();

    public static void main(String[] args) {
        int n = 4;
        List<List<String>> res = (new Nqueue()).solveNqueues(n);
        for (List<String> board : res) {
            printBoard(board);
        }
    }

    private static void printBoard(List<String> board) {
        for (String s : board)
            System.out.println(s);
        System.out.println();
    }

    public List<List<String>> solveNqueues(int n) {

        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];
        LinkedList<Integer> row = new LinkedList<Integer>();
        putQueen(n, 0, row);
        return res;
    }

    private void putQueen(int n, int index, LinkedList<Integer> row) {
        if (index == n) {
            res.add(generateBoard(n, row));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                row.add(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, row);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.removeLast();
            }

        }
    }

    private List<String> generateBoard(int n, LinkedList<Integer> row) {
        assert (row.size() == n);
        ArrayList<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[row.get(i)] = 'Q';
            board.add(new String(charArray));
        }
        return board;
    }


}