easy to understand c++ 4ms solution


  • 0
    R

    class Solution {
    public:

    vector<int> rows;//check a row has queen
    vector<int> cols;//check a col has queen
    vector<int> d1;  // check a diagonal has queen
    vector<int> d2;	// check another diagonal has queen
    
    vector<vector<string>> solveNQueens(int n) {
    	//init
    	rows = vector<int>(n, 0);
    	cols = vector<int>(n, 0);
    	d1 = vector<int>(2*n-1, 0);
    	d2 = vector<int>(2*n-1, 0);
    	vector<vector<string>> result;
    	vector<string> board;
    	string s;
    	for (int i = 0; i < n; i++)
    		s += '.';
    	for (int i = 0; i < n; i++)
    		board.push_back(s);
    	//solve
    	solveRecursive(0, n, result, board);
    	return result;
    }
    
    //if a place can put queen?
    bool ValidQueen(int i, int j, int n) {
    	if (rows[i] == 0 && cols[j] == 0 && d1[i + j]==0 && d2[n - i - 1 + j] == 0) {
    		return true;
    	}
    	else
    		return false;
    }
    void PutQueen(int i, int j, int n, vector<string>& board) {
    	board[i][j] = 'Q';
    	rows[i] = 1;
    	cols[j] = 1;
    	d1[i + j] = 1;
    	d2[n - i - 1 + j] = 1;
    }
    void DeleteQueen(int i, int j, int n, vector<string>& board) {
    	board[i][j] = '.';
    	rows[i] = 0;
    	cols[j] = 0;
    	d1[i + j] = 0;
    	d2[n - i - 1 + j] = 0;
    }
    void solveRecursive(int startRow, int n, vector<vector<string>>& result, vector<string>& board) {
    	
    	if (startRow == n) {
    		result.push_back(board);
    		return;
    	}
    	int i = startRow;
    	for (int j = 0; j < n;j++){//choose a col to put queen
    		if(!ValidQueen(i,j,n)) continue;
    		PutQueen(i, j, n, board);
    		solveRecursive(startRow + 1, n, result, board);
    		DeleteQueen(i, j, n, board);
    	}
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.