자바 와 N 황후 (leetcode 51)

leetcode 51 번, N 황후.해결 의 핵심 적 인 사 고 는 재 귀 + 역 추적 으로 해 수 독 의 사고 와 유사 하 다.
class Solution {
    

    public List> solveNQueens(int n) {
        List> list = new ArrayList<>();
        char [][]cs = new char[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                cs[i][j] = '.';
            }
        }
        putQueen(list, 0, n, cs);
        return list;
    }

	// 尝试放置:递归+回溯
    private void putQueen(List> list, int row, int n,char [][]cs) {


        if (row == n) {
            List l = new ArrayList();
            for(int i = 0;i < n;i++){
                l.add(new String(cs[i]));
            }
            list.add(l);
            return;
        }

        for (int i = 0; i < n; i++) {
            for(int j = 0;j < n;j++){
                cs[row][j] = '.';
            }
            cs[row][i] = 'Q';
            if (isSafety(cs, row, i, n)) {
                putQueen(list, row + 1, n, cs);
            }
        }

    }

	// 检测放置的皇后是否有问题 
    private boolean isSafety(char[][]cs, int row, int col, int n) {
        int step = 1;
        while (row - step >= 0) {
            if (cs[row-step][col] == 'Q') {
                return false;
            }
            if (col - step >= 0 && cs[row-step][col-step] == 'Q') {
                return false;
            }
            if (col + step < n && cs[row-step][col+step] == 'Q') {
                return false;
            }
            step ++;
        }
        return true;
    }
    
}

좋은 웹페이지 즐겨찾기