13ms C++ recursion and backtracking


  • 0
    M
    class Solution {
    public:
    	bool possible(int row, int col, vector<string> &temp, vector<int> &ColOfRow)
    	{
    		for(int i=0;i<row;i++)
    		{
    			if(temp[i][col] == 'Q')
    				return false;
    			if(fabs(row-i) == fabs(col-ColOfRow[i]))
    				return false;
    		}	
    		return true;
    	}
    	
    	void recSolve(int row, int n, vector<string> &temp, vector<vector<string> > &res,
    					vector<int> &ColOfRow)
    	{
    		if(n==row)
    		{
    			res.push_back(temp);
    			return;
    		}
    		for( int col=0;col<n;++col)
    		{
    			//If possible, Keep a queen in the col; try for next row;
    			if(possible(row, col, temp, ColOfRow))
    			{
    				temp[row][col] = 'Q';
    				ColOfRow[row] = col;
    				recSolve(row+1, n, temp, res , ColOfRow);
    				temp[row][col] = '.';
    			}
    		}
    	}
    	
        vector<vector<string> > solveNQueens(int n) {
            vector<vector<string> > res;
            	vector<string> temp(n, string(n, '.'));//Each string has 9 dots
            	vector<int> ColOfRow(n, -1);
    			recSolve(0, n, temp, res, ColOfRow);
    			return res;
        }
    };

Log in to reply
 

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