leetcode 51. N-Queens

    xiaoxiao2021-03-25  8

    题目链接:点击打开链接 题目:

    The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

    Given an integer n, return all distinct solutions to the n-queens puzzle.

    Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

    For example, There exist two distinct solutions to the 4-queens puzzle:

    [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

    思路:

    采用经典解法回溯递归,一层一层的向下扫描,需要用到一个columns数组,其中columns[row] = col表示row行col列存在皇后,从0行开始递归,每一行都依次遍历各列,判断如果在该位置放置皇后会不会有冲突,以此类推,当到最后一行的皇后放好后,一种解法就生成了,将其存入结果result中,然后继续完成搜索所有的情况

    代码AC:

    public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<List<String>>(); //columns[row] = col表示在row行col列放置queen int[] columns = new int[n]; solveNQueens(0, columns, result, n); return result; } public void solveNQueens(int row, int[] columns, List<List<String>> result, int n){ if(row == n){ //找到有效的摆法 List<String> str = new ArrayList<String>(); for(int i = 0; i < n; i++ ){ String s = ""; for(int k = 0; k < n; k++){ s+="."; } str.add(s); } for(int j = 0; j < n; j++){ StringBuilder strBuilder = new StringBuilder(str.get(j)); strBuilder.setCharAt(columns[j], 'Q'); str.set(j, strBuilder.toString()); } result.add(str); }else{ for(int col = 0; col < n; col++){ if(checkValid(columns, row, col)){ columns[row] = col; //摆放皇后 solveNQueens(row+1, columns, result, n); } } } } public boolean checkValid(int[] columns, int row, int col){ for(int tempRow = 0; tempRow < row; tempRow++){ //若两个皇后在同一列,则无效 if(columns[tempRow] == col) return false; //若两个皇后在对角线则无效 if(Math.abs(columns[tempRow]-col)== row-tempRow) return false; } return true; } }

    转载请注明原文地址: https://ju.6miu.com/read-200176.html

    最新回复(0)