TLE in one input


  • 0
    T

    Hi,

    I use back approach in this question, and when deciding whether a number is valid, I only check if this number exist in the current row, current column or current "cube", but it still got TLE in this input....

    Last executed input: ["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]

        class Solution {
    public:
        bool solve(int i,int j,vector<vector<char> > &board,vector<vector<bool> >& each_row,vector<vector<bool> >& each_column,vector<vector<bool> >& each_cube){
            
            if(9==i && 0==j)
                return true;
                
            int next_j=(j+1)%9;
            int next_i=i+(j+1)/9;
            
            if(board[i][i]!='.')
                return solve(next_i,next_j,board,each_row,each_column,each_cube);
            
            //try to fill
            for(int n=1;n<10;n++){
                if(each_row[i][n]==true && each_column[j][n]==true && each_row[(i/3)*3+j/3][n]==true){
                    each_row[i][n]=false;
                    each_column[j][n]=false;
                    each_row[(i/3)*3+j/3][n]=false;
                    
                    board[i][j]=n+'0';
                    if(solve(next_i,next_j,board,each_row,each_column,each_cube))
                        return true;
                    
                    
                    each_row[i][n]=true;
                    each_column[j][n]=true;
                    each_row[(i/3)*3+j/3][n]=true;
                }
                
            }
            
            board[i][j]='.';
            return false;
        }
        
        void solveSudoku(vector<vector<char> > &board) {
            vector<vector<bool> > each_row(9);
            for(int i=0;i<9;i++)
                each_row[i].assign(10,true);
                
            vector<vector<bool> > each_column=each_row;
            vector<vector<bool> > each_cube=each_row;
            
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][i]!='.'){
                        int n=board[i][i]-'0';  
                        each_row[i][n]=false;
                        each_column[j][n]=false;
                        each_cube[(i/3)*3+j/3][n]=false;}
                }
            }
            
            solve(0,0,board,each_row,each_column,each_cube);
            
            return;
        }
    };

  • 0
    S

    There are so many typo in your code, like if(board[i][i]!='.') each_row[(i/3)*3+j/3][n]=true; etc . I believe these are the reason to TLE.

    I think you might use copy-paste to implement your algorithm, it is not a good habit.

    However, for these problem, you can use 1d integer array instead of 2d bool array to do the valid check, each bit of integer can be 0 or 1, just like boolean. Integer has 31 bit, so 9 bits is enough for 1-9.


Log in to reply
 

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