diff options
Diffstat (limited to 'n_queens.cpp')
-rw-r--r-- | n_queens.cpp | 43 |
1 files changed, 0 insertions, 43 deletions
diff --git a/n_queens.cpp b/n_queens.cpp deleted file mode 100644 index df2457e..0000000 --- a/n_queens.cpp +++ /dev/null @@ -1,43 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<vector<string>> solveNQueens(int n) { - vector<vector<string>> ans; - vector<string> nQueens(n, string(n, '.')); - solve(ans, nQueens, 0, n); - return ans; - } - -private: - void solve(vector<vector<string>> &ans, vector<string> &nQueens, int row, - int &n) { - if (row == n) { - ans.push_back(nQueens); - return; - } - for (int col = 0; col != n; ++col) - if (isValid(nQueens, row, col, n)) { - nQueens[row][col] = 'Q'; - solve(ans, nQueens, row + 1, n); - nQueens[row][col] = '.'; - } - } - bool isValid(vector<string> &nQueens, int row, int col, int &n) { - // check if col had queen - for (int i = 0; i != row; ++i) - if (nQueens[i][col] == 'Q') - return false; - // check if 45deg diagonal had queen - for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) - if (nQueens[i][j] == 'Q') - return false; - // check if 135deg diagonal had queen - for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) - if (nQueens[i][j] == 'Q') - return false; - return true; - } -}; - -int main() {} |