LeetCode51—N皇后

递归 搜索 剪枝

第一次提交代码：(递归+搜索）

class Solution {
    public List<List<String>> solveNQueens(int n) 
    {
        List<List<String>> Ans=new ArrayList<List<String>>();
        //新建List类型数据结构时需指定像ArrayList这样的接口
        char[][] Map=new char[n][n];
        for(int i=0;i<n;i++) 
            for(int j=0;j<n;j++)
                Map[i][j]='.';//棋盘初始化
        DFS(Ans,Map,0,n);
        return Ans;
    }
    public void DFS(List<List<String>> Ans,char[][] Map,int t,int n)
    //枚举放皇后的方案，其中t指已放皇后的个数
    {
        if(t==n)//皇后放完了，生成可行方案加入Ans
        {
            List<String> list=new ArrayList<String>();
            for(int i=0;i<n;i++) list.add(String.valueOf(Map[i]));
            //String.valueOf()可将一个变量或数组转化成字符串
            Ans.add(list);
            return;
        }
        for(int i=0;i<n;i++)
        if(check(Map,t,i,n))//检测是否能放皇后
        {
            Map[t][i]='Q';
            DFS(Ans,Map,t+1,n);
            Map[t][i]='.';//枚举完要复原
        }
    }
    public boolean check(char[][] Map,int x,int y,int n)
    //判断是否能放皇后的函数。（x,y）指放置位置的坐标。
    {
        for(int i=0;i<n;i++)
            if(i!=x&&Map[i][y]=='Q') return false;//同列判断
        for(int i=1;i<n;i++)
        {
            if(x-i>=0&&y-i>=0&&Map[x-i][y-i]=='Q') return false;//对角线判断
            if(x-i>=0&&y+i<n&&Map[x-i][y+i]=='Q') return false;
            if(x+i<n&&y-i>=0&&Map[x+i][y-i]=='Q') return false;
            if(x+i<n&&y+i<n&&Map[x+i][y+i]=='Q') return false;
        }
        return true;
    }
}

第二次提交代码：（递归+搜索+剪枝）

class Solution 
{
    List<List<String>> Ans=new ArrayList<List<String>>();
    char[][] Map;
    public List<List<String>> solveNQueens(int n) 
    {
        Map=new char[n][n];
        for(int i=0;i<n;i++) 
            for(int j=0;j<n;j++)
                Map[i][j]='.';
        DFS(0,n);
        return Ans;
    }
    public void DFS(int t,int n)
    {
        if(t==n)
        {
            List<String> list=new ArrayList<String>();
            for(int i=0;i<n;i++) list.add(String.valueOf(Map[i]));//String.valueOf()可将一个变量或数组转化成字符串
            Ans.add(list);
            return;
        }
        for(int i=0;i<n;i++)
        if(check(t,i,n))//检测是否能放皇后
        {
            Map[t][i]='Q';
            DFS(t+1,n);
            Map[t][i]='.';
        }
    }
    public boolean check(int x,int y,int n)
    {
        for(int i=0;i<x;i++)
            if(Map[i][y]=='Q') return false;
        for(int i=1;i<n;i++)
        {
            if(x-i>=0&&y-i>=0&&Map[x-i][y-i]=='Q') return false;
            if(x-i>=0&&y+i<n&&Map[x-i][y+i]=='Q') return false;
        }
        return true;
    }
}