I'm trying to do this nQueens problem and my code looks like this:
class Solution {
public:
vector<vector<string>> ans;
bool canPlace(vector<string> &board, int row, int col, int n){
//upper left diagonal
int rowIndex = row;
int colIndex = col;
while(rowIndex >= 0 and colIndex >= 0){
if(board[rowIndex][colIndex] == 'Q'){
return false;
}
rowIndex--;
colIndex--;
}
// left side
rowIndex = row;
colIndex = col;
while(colIndex >= 0){
if(board[rowIndex][colIndex] == 'Q'){
return false;
}
colIndex--;
}
// left side
rowIndex = row;
colIndex = col;
while(rowIndex < n and colIndex >= 0){
if(board[rowIndex][colIndex] == 'Q'){
return false;
}
rowIndex++;
colIndex--;
}
return true;
}
void nQueens(vector<string> &board, int col, int n){
if(col == n){
ans.push_back(board);
for(int i = 0; i < n; i++){
cout<<board[i]<<", ";
}
cout<<endl;
return;
}
for(int row = 0; row < n; row++){
if(canPlace(board, row, col, n)){
cout<<"Changing board from: "<<board[row][col]<<endl;
board[row][col] = 'Q';
nQueens(board, col+1,n);
board[row][col] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n);
string s(n, '.');
for(int i = 0; i < n; i++){
board[i] = s;
// push_back gives weird result
}
nQueens(board, 0, n);
return ans;
}
};
In the last solveNQueens function. Inside the for loop, if I use board.push_back(s)
instead of board[i] = s
, leetcode throws a Wrong Answer error and the output when using cout shows weird random symbols.
Why is this? Shouldn't push_back give the same results? I'd love to know why this happens.
Here's the link to the leetcode problem: https://leetcode.com/problems/n-queens
vector<string> board(n);
fills the vector already with n
elements. If you now add additional! elements with push_back
, you have a vector with two times elements. The first half are already in from the constructor of std::vector
and the second half pushed in later.
If you use the default constructor
vector<string> board;
in combination with push_back
, you will get the same results as with your example code.
For large vectors the solution with upfront initialization of n
elements and access via operator[]
can be much faster, because there is no need of reallocation and copy operations inside the vector. If speed is important: measure!