My Accepted Code 48ms using Hashcode and DFS


  • -1
    Z
    struct pos
    {
    	int i;`enter code here`
    	int j;
    };
    class Solution {
    private:
    	int cols;
    	int rows;
    	int postoint(pos _pos)
    	{
    		return _pos.i*cols + _pos.j;
    	}
    	pos inttopos(int myint)
    	{
    		pos mypos;
    		mypos.j = myint%cols;
    		mypos.i = myint / cols;
    		return mypos;
    	}
    private:
    	void removeFrompos(unordered_set<int>::iterator &it, unordered_set<int>& mypos, int rows, int cols)
    	{
    		int currentposint = *it;
    		if (mypos.find(currentposint) == mypos.end())
    			return;
    		else
    		    mypos.erase(it);
    		pos leftpos, rightpos, uppos, downpos;
    		pos currentpos = inttopos(currentposint);
    		if (currentpos.i>0)
    		{
    			uppos.i = currentpos.i - 1;
    			uppos.j = currentpos.j;
    			int upposint = postoint(uppos);
    			unordered_set<int>::iterator _it = mypos.find(upposint);
    			if(_it!=mypos.end())
    			    removeFrompos(_it, mypos, rows, cols);
    		}
    		if (currentpos.i<rows - 1)
    		{
    			downpos.i = currentpos.i + 1;
    			downpos.j = currentpos.j;
    			int downposint = postoint(downpos);
    			unordered_set<int>::iterator _it = mypos.find(downposint);
    			if(_it!=mypos.end())
    			    removeFrompos(_it, mypos, rows, cols);
    		}
    		if (currentpos.j>0)
    		{
    			leftpos.j = currentpos.j - 1;
    			leftpos.i = currentpos.i;
    			int leftposint = postoint(leftpos);
    			unordered_set<int>::iterator _it = mypos.find(leftposint);
    			if(_it!=mypos.end())
    			    removeFrompos(_it, mypos, rows, cols);
    		}
    		if (currentpos.j<cols - 1)
    		{
    			rightpos.j = currentpos.j + 1;
    			rightpos.i = currentpos.i;
    			int rightposint = postoint(rightpos);
    			unordered_set<int>::iterator _it = mypos.find(rightposint);
    			if(_it!=mypos.end())
    			    removeFrompos(_it, mypos, rows, cols);
    		}
    	}
    public:
    	int numIslands(vector<vector<char>>& grid) {
    		unordered_set<int> mypos;
    		if(grid.size()==0)
    		    return 0;
    		rows = grid.size();
    		cols = grid[0].size();
    		for (int i = 0; i<grid.size(); i++)
    		{
    			for (int j = 0; j<grid[i].size(); j++)
    			{
    				if (grid[i][j] == '1')
    				{
    					pos p;
    					p.i = i;
    					p.j = j;
    					int myint = postoint(p);
    					mypos.insert(myint);
    				}
    			}
    		}
    		int count = 0;
    		unordered_set<int>::iterator it;
    		while (mypos.size() != 0)
    		{
    			it = mypos.begin();
    			removeFrompos(it, mypos, grid.size(), grid[0].size());
    			count++;
    		}
    		return count;
    	}
    };

Log in to reply
 

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