Share my simple c++ code with using unsorted_set


  • 0
    D
    class Solution {
    public:
    	bool dfs(vector<vector<char>>& board, int i, int j)
    	{
    		while(i<=8 && j<=8 && board[i][j] != '.')//find next empty cell
    		{
    			if(j==8)                //find empty cell in next row
    			{
    				j=0;
    				++i;
    			}
    			else if(j<8)            // find empty cell in next col
    				++j;
    		}
    
    		if(i==9)                // i==9 means all the cells are filled 
    			return true;
    		char n;
    		int x = i / 3;
    		int y = j / 3;
    		for(int k=1; k<=9; ++k)
    		{
    			n = k+'0';          // enumerate all possible digit
    			if(row[i].find(n) == row[i].end() && col[j].find(n) == col[j].end() && cell[x][y].find(n) == cell[x][y].end())
    			{
    				row[i].insert(n);
    				col[j].insert(n);
    				cell[x][y].insert(n);
    				board[i][j] = n;
    				if(dfs(board,i,j))  
    					return true;
    				else
    				{
    					row[i].erase(n);
    					col[j].erase(n);
    					cell[x][y].erase(n);
    					board[i][j] = '.';
    				}
    			}
    		}
    		return false;
    	}
        void solveSudoku(vector<vector<char>>& board) {
    		for(int i=0; i<9; ++i)        
    			for(int j=0; j<9; ++j)
    			{
    				if(board[i][j] != '.')
    				{
    					int x = i / 3;
    					int y = j / 3;
    					row[i].insert(board[i][j]);
    					col[j].insert(board[i][j]);
    					cell[x][y].insert(board[i][j]);
    				}
    			}
    		dfs(board,0,0);
    		return;
        }
    private:
    	unordered_set<char> row[9];
    	unordered_set<char> col[9];
    	unordered_set<char> cell[3][3];  
    };

  • 0
    I

    For an application like this, where you only have 9 items and they're numerically consecutive, a std::bitset<> is a much better choice than std::unordered_set<>. Both are O(1), but bitset doesn't require computing a hash. Also, since its size is fixed at compile time, it doesn't require dynamic memory allocation either.

    http://en.cppreference.com/w/cpp/utility/bitset


Log in to reply
 

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