题目

image.png

思路

  • 回溯老套路

    代码

    1.   List<List<String>> res;
    2.   List<String> list;
    3.   int[][] visited;
    4.   char[] arr;
    5.   public List<List<String>> solveNQueens(int n) {
    6.       res = new ArrayList<>();
    7.       list = new ArrayList<>();
    8.       visited = new int[n][n];
    9.       arr = new char[n];
    10.       for (int i = 0; i < n; i++) {
    11.           arr[i] = '.';
    12.       }
    13.       dfs(n, 0);
    14.       return res;
    15.   }
    17.   public void dfs(int n, int m) {
    18.       if (m == n && list.size() < n) return;
    19.       if (m == n && list.size() == n) {
    20.           res.add(new ArrayList<>(list));
    21.           return;
    22.       }
    23.       for (int i = 0; i < n; i++) {
    24.           if (visited[m][i] > 0) continue;
    25.           arr[i] = 'Q';
    26.           //添加字符串
    27.           list.add(new String(arr));
    28.           arr[i] = '.';
    29.           //设置不可访问位
    30.           for (int j = m, l = i, r = i; j < n; j++, l--, r++) {
    31.               visited[j][i]++;
    32.               if (l >= 0) visited[j][l]++;
    33.               if (r < n) visited[j][r]++;
    34.           }
    35.           dfs(n, m + 1);
    36.           //撤销不可访问位
    37.           for (int j = m, l = i, r = i; j < n; j++, l--, r++) {
    38.               visited[j][i]--;
    39.               if (l >= 0) visited[j][l]--;
    40.               if (r < n) visited[j][r]--;
    41.           }
    42.           //移除字符串
    43.           list.remove(list.size() - 1);
    44.       }
    45.   }

    N皇后