[leetcode] N-Queens | 8皇后问题

Posted by: lexigrey on: August 2, 2013

• In: classic | leetcode
• 1 Comment

这题做了好几遍了，（尽管每次都有进步）但是因为一直用的二维数组char[][] board，到leetcode上跑才发现超时。问题出现在算“对角能不能放”的时候，因为char[][]要遍历才能知道之前都在哪些位置放了皇后，所以多花了遍历的时间。书上的算法是用int[] queenColAtRow，这样queenColAtRow[i]就表示“在第i行，把queen放在了result位置上“。这样可以直接O(1)的知道每行queen都放在哪列了，少遍历一维，大的就过了。

public int totalNQueens(int n) {
  ArrayList<String[]> solveNQueens = solveNQueens(n);
  return solveNQueens.size();
}
public ArrayList<String[]> solveNQueens(int n) {
  //生成全是.的board，因为要返回board本身，所以现在先填好了。
  char[][] board = new char[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      board[i][j] = '.';
    }
  }
  ArrayList<String[]> result = new ArrayList<String[]>();
  placeQueen(board, 0, n, result);
  return result;
}
private void placeQueen(char[][] board, int row, int n, ArrayList<String[]> result) {
  if (row == n) {
    result.add(copyBoard(board));
    return;
  }
  for (int col = 0; col < n; col++) {
    if (canPlace(board, row, col)) {
      board[row][col] = 'Q';
      placeQueen(board, row + 1, n, result);
      board[row][col] = '.';
    }
  }
}
private boolean canPlace(char[][] board, int row, int col) {
  // row is definitely fine
  for (int i = 0; i <= row; i++) {
    if (board[i][col] == 'Q')
      return false;
  }
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < board.length; j++) {
      if (board[i][j] == 'Q' && Math.abs(i - row) == Math.abs(j - col))
      return false;
    }
  }
  return true;
}

Advertisements

Tags: dfs, easy, matrix