一天十道题，走起！

皇后2，好蠢

1. class Solution {
   
2.      int[] X = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
   
3.      int[] Y = new int[]{0, 0, -1, 1, -1, 1, -1, 1};
   
4.      int res = 0;
   
5. 
   
6.      List<List<String>> result = new ArrayList<>();
   
7. 
   
8.     public int totalNQueens(int n) {
   
9. 
   
10.         boolean[][] grid = new boolean[n][n];
    
11.         helper(grid, n, 0, 0, new ArrayList<>());
    
12.         return res;
    
13. 
    
14.     }
    
15. 
    
16.     private void helper(boolean[][] grid, int k, int mStart, int nStart, List<String> list) {
    
17.         if (k == 0) {
    
18.             result.add(new ArrayList<>(list));
    
19.             res = res + 1;
    
20.             return;
    
21.         }
    
22. 
    
23.         // for every possible grid, try this!
    
24.         for (int m = mStart; m < grid.length; m++) {
    
25.             for (int n = nStart; n < grid.length; n++) {
    
26.                 if (grid[m][n] == false) {
    
27. 
    
28.                     boolean[][] tmp = new boolean[grid.length][grid.length];
    
29.                     for (int i = 0; i < grid.length; i++) {
    
30.                         for (int j = 0; j < grid.length; j++) {
    
31.                             tmp[i][j] = grid[i][j];
    
32.                         }
    
33.                     }
    
34. 
    
35.                     sink(grid, m, n);
    
36.                     list.add(m + "," + n);
    
37.                     helper(grid, k - 1, m, 0, list);
    
38.                     list.remove(list.size() - 1);
    
39.                     for (int i = 0; i < grid.length; i++) {
    
40.                         for (int j = 0; j < grid.length; j++) {
    
41.                             grid[i][j] = tmp[i][j];
    
42.                         }
    
43.                     }
    
44. //                    unSink(grid, m, n);
    
45.                 }
    
46.             }
    
47.         }
    
48. 
    
49.     }
    
50. 
    
51. 
    
52.     //mark all the places as dot
    
53.     private boolean[][] sink(boolean[][] grid, int i, int j) {
    
54.         grid[i][j] = true;
    
55.         for (int dir = 0; dir < 8; dir++) {
    
56.             int x = i + X[dir];
    
57.             int y = j + Y[dir];
    
58. 
    
59.             while (x >= 0 && x < grid.length && y >= 0 && y < grid.length) {
    
60.                 grid[x][y] = true;
    
61.                 x += X[dir];
    
62.                 y += Y[dir];
    
63.             }
    
64.         }
    
65.         return grid;
    
66.     }
    
67. 
    
68.     //mark all the places as dot
    
69.     private boolean[][] unSink(boolean[][] grid, int i, int j) {
    
70.         grid[i][j] = false;
    
71.         for (int dir = 0; dir < 8; dir++) {
    
72.             int x = i + X[dir];
    
73.             int y = j + Y[dir];
    
74. 
    
75.             while (x >= 0 && x < grid.length && y >= 0 && y < grid.length) {
    
76.                 grid[x][y] = false;
    
77.                 x += X[dir];
    
78.                 y += Y[dir];
    
79.             }
    
80.         }
    
81.         return grid;
    
82.     }
    
83. }

复制代码