Time limit exceeded....please help..


  • 0
    T

    class Solution {

    void NQueens(vector<string>& grid,vector<vector<string>>& result,int col,int size)
    {
        if(col == size)
        {
            result.push_back(grid);
            return;
        }
    
        for(int row = 0;row < size;row++)
        {
            if(IsSafe(grid,row,col,size) == true)
            {
                grid[row][col] = 'Q';
                NQueens(grid,result,col + 1,size);
                grid[row][col] = '.';
            }
        }
    }
    
    bool IsSafe(vector<string>& grid,int row,int col,int size)
    {
        for(int i = 0;i < col;i++)
            if(grid[i][col] == 'Q')
                return false;
    
        for(int i = row,j = col;i >= 0 && j >= 0;i--,j--)
            if(grid[i][j] == 'Q')
                return false;
    
        for(int i = row,j = col;j >= 0 && i < size;i++,j--)
            if(grid[i][j] == 'Q')
                return false;
    
        return true;
    }
    

    public:

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        if(n == 0)
            return result;
    
        vector<string> grid(n,string(n,'.'));
    
        NQueens(grid,result,0,n);
        return result;
    }
    

    };


  • 1
    T

    Hi,
    You made a mistake in the IsSafe function. Instead of checking rows you checked columns.

    Change from this:

      for(int i = 0;i < col;i++)
        if(grid[i][col] == 'Q')
            return false;
    

    To this:

      for(int i = 0 ; i < col;i++)
            if(grid[row][i] == 'Q')
                return false;

  • 0
    T

    I got it....It got accepted now.... Thanks for your help


  • 0
    T

    could you select my answer as best?


Log in to reply
 

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