LeetCode-51.N皇后

 1 import java.util.ArrayList;
 2 class Solution {
 3     private List<List<String>> result;
 4     public List<List<String>> solveNQueens(int n) {
 5         char [][]array=new char [n][n];
 6         result=new ArrayList<>();
 7         //初始化数组
 8         for(int i=0;i<n;i++)
 9             for(int j=0;j<n;j++)
10                 array[i][j]='.';
11         //先横再竖，全部规则符合时，切换到下一行
12         solveNQueens(array,0);
13         return result;
14     }
15     //参数n为数组行
16     public void solveNQueens(char [][]array,int n) {
17         int num=array.length;
18         //当n==num时，即为所有行数都已填入，此时处理array
19         if(n==num){
20             Deal(array);
21             return ;
22         }
23         for(int i=0;i<num;i++){
24             //每一位插入Q
25             array[n][i]='Q';
26             //因为从第一行开始填入，所以只需要进行从第一行到n行的检查
27             //分别为竖列的检查和斜的检查
28             if(checkj(array,n,i)&&checkij(array,n,i)){
29                 //如果都符合规则的话就进入下一行
30                 solveNQueens(array,n+1);
31             }
32             //当递归完成后或者不符合规则的时候更改回'.'
33             array[n][i]='.';
34         }
35     }
36     //处理array
37     private void Deal(char[][] array){
38         int num=array.length;
39         List<String> list=new ArrayList<>();
40         for(int i=0;i<num;i++){
41             String str="";
42             for(int j=0;j<num;j++){
43                 str+=array[i][j];
44             }
45             list.add(str);
46         }
47         result.add(list);
48     }
49     //检查竖的
50     private boolean checkj(char [][]array,int i,int j){
51         for(int m=0;m<i;m++){
52             if(array[m][j]=='Q')
53                 return false;
54         }
55         return true;
56     }
57     //检查斜的
58     private boolean checkij(char [][]array,int i,int j){
59         int num=array.length;
60         int tmpi=i,tmpj=j;
61         //从左上到该坐标
62         while(tmpi>0&&tmpj>0){
63             tmpi--;
64             tmpj--;
65         }
66         //寻找临界点
67         while(tmpi<i&&tmpj<j){
68             if(array[tmpi][tmpj]=='Q')
69                 return false;
70             tmpi++;
71             tmpj++;
72         }
73         //从右上到该坐标
74         tmpi=i;
75         tmpj=j;
76         //寻找临界点
77         while(tmpi>0&&tmpj<num-1){
78             tmpi--;
79             tmpj++;
80         }
81         while(tmpi<i&&tmpj>j){
82             if(array[tmpi][tmpj]=='Q')
83                 return false;
84             tmpi++;
85             tmpj--;
86         }
87         return true;
88     }
89 }