MENU

LeetCode51. N皇后

July 14, 2018 • Read: 220 • LeetCode

image

 我博客里有写过很多关于n皇后的教程,直接搜索关键字即可,这里就不多说了

class Solution {
    public List<List<String>> ans = new ArrayList<List<String>>();
    public int path[] = new int[100];//path[i]表示第i行的皇后位置在第path[i]列
    public void dfs(int idx,int n) {//idx = 行
        int p;
        if(idx >= n) {
            List<String> check = new ArrayList<String>();
            for(int i = 0;i < n;i++) {
                String tmp = "";
                for(int j = 0;j < n;j++) {
                    if(j == path[i])
                        tmp += "Q";
                    else
                        tmp += ".";
                }
                check.add(tmp);
            }
            ans.add(check);
            return;
        }
        for(int i = 0;i < n;i++) {//枚举n列
            for(p = 0;p < idx;p++) {//和前k行皇后做比较
                if(path[p] == i || Math.abs(p - idx) == Math.abs(path[p] - i))
                    break;
            }
            if(idx == p) {
                path[p] = i;
                dfs(idx + 1,n);
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        ans.clear();
        dfs(0,n);
        return ans;
    }
}
最后编辑于: August 12, 2018
Archives Tip
QR Code for this page
Tipping QR Code