#LeetCode:52. N-Queens II

rowcolumn 為主,進行 backtracking 法去放置各個皇后看看是否可以成功放置,這樣即可得解。

C++(8ms)

/*******************************************************/
/* LeetCode 52. N-Queens II                            */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/16                                 */
/*******************************************************/
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
  int backtrackingGetTotalNQueens(
    int n,
    int row,
    vector<bool> &rowCheck,
    vector<bool> &columnCheck,
    vector<bool> &slashCheck,
    vector<bool> &backslashCheck){

    if(row >= n){
      return 1;
    }

    int total = 0;
    for(int column = 0 ; column < n ; ++column){
      int slashIndex = row + column;
      int backSlashIndex = row - column + n - 1;
      if(!rowCheck[row] && !columnCheck[column] && 
        !slashCheck[slashIndex] && !backslashCheck[backSlashIndex]){
        rowCheck[row] = true;
        columnCheck[column] = true;
        slashCheck[slashIndex] = true;
        backslashCheck[backSlashIndex] = true;

        total += backtrackingGetTotalNQueens(n, row+1,
          rowCheck, columnCheck, slashCheck, backslashCheck);

        rowCheck[row] = false;
        columnCheck[column] = false;
        slashCheck[slashIndex] = false;
        backslashCheck[backSlashIndex] = false;
      }
    }

    return total;
  }

  int totalNQueens(int n) {
      vector<bool> rowCheck(n, false);
      vector<bool> columnCheck(n, false);
      vector<bool> slashCheck(2 * n - 1, false);
      vector<bool> backslashCheck(2 * n - 1, false);

      return backtrackingGetTotalNQueens(
        n, 0, rowCheck, columnCheck, slashCheck, backslashCheck);
  }
};

1 回應

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: