How can I modify my C++ code ?


  • 0
    L
       void solveNQueens_iter(int *solution,int row,int n,vector<vector<string> >&result){
    
       int i;
       int j;
       if( row == n ){
          vector<string>temp;
          temp.clear();
          for(i=0;i<n;i++){
             for(j=0;j<n;j++){
                if( solution[i] == j){
                     temp.push_back("Q");
                }
                else{
                    temp.push_back(".");
                }
            }
         }
         //cnt++;
         result.push_back(temp);
         return;
       }
       int col ;
       int check;
       int next_row;
       for(col=0;col<n;col++){
           next_row = 1;
           for(check=0;check<row;check++){
              if( (solution[check] == col) ||
                  (abs(row-check) == abs(col-solution[check])) ){
                    next_row = 0;
                    break;
              }
           }
    
           if(next_row){
              solution[row] = col;
              solveNQueens_iter(solution,row+1,n,result);
           }
    
       }
    }
    
    
    
    vector<vector<string> > solveNQueens(int n){
    
       vector<vector<string> > result;
    
       int solution[n];
    
       int i;
       for(i=0;i<n;i++){
          solution[i] = -1;
       }
        solveNQueens_iter(solution,0,n,result);
       return result;
    
    }
    

    This is my code,but it report output limit exceed.
    How can I modify it?
    In my machine,it cost too long when N is 16.


  • 0
    A

    It's an output limit, not a time limit, possibly due to the fact you are pushing back the solution when temp has already been destroyed (out of scope).

       if( row == n ){
          vector<string>temp; <--- temp STARTS living here
          temp.clear(); <----- By the way, no need to clear here, it's a new vector!
          for(i=0;i<n;i++){
             for(j=0;j<n;j++){
                if( solution[i] == j){
                     temp.push_back("Q");
                }
                else{
                    temp.push_back(".");
                }
            }
         } <--- temp DIES here
         //cnt++;
         // ERROR: temp is undefined here!
         result.push_back(temp);
    

    I'm surprised this program even got compiled O.o

    Additionally, each element of temp is a row of the solution, not just a character. So each time you are calling "push_back" you are creating a solution like:

    "Q"

    "."

    "."

    "Q"

    "."

    Instead of

    "Q..."

    "..Q."

    etc

    My version uses the same idea as yours, but it's a bit simpler. Maybe you can check it out to see what I mean:

    https://oj.leetcode.com/discuss/20754/c-10ms-o-n-memory

    Good luck!


Log in to reply
 

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