Easy To Understand and Explained C++ Solution


  • 0
    V

    Steps -

    1. Traverse matrix, If you see a '1' , then bfs matrix to all possible 0's in the matrix from current point.

    2. While in bfs, if you see a '0' and if it is a feasible node to visit, then add the shortest distance from that particular '1' to the map sumoflocaldist. Then add sumoflocaldist to the map containing the sum of distances from all the '1's seen so far (sumofdist) to that '0'. Also update the the feasibility map for the '0' by 1 to indicate that we can reach this point from the current '1'.

    3. Increment numofones count after completing bfs.

    4. Traverse matrix from start again and now if you see a '0', all we do is look at the feasibility map (should be equal to numofones so that we can reach this '0' from all '1's) and sumofdist map and check if sumofdist<min.

    5. If so, update min.

    class Solution {
    public:
    
        void shortestpathtraversal(int row,int col,int m,int n,map <pair<int,int>,int>& sumofdist,vector<vector<int>>& grid,map <pair<int,int>,int>& feasibility,int numofones)
        {
            vector<vector<int>> visited(m,vector<int>(n,0));
            queue<pair<int,int>> traversal;
            pair<int,int> temp;
            map <pair<int,int>,int> sumoflocaldist;
            int i,j;
            traversal.push(make_pair(row,col));
            sumoflocaldist[make_pair(row,col)]=0;
            visited[row][col]=1;
            while(!traversal.empty())
            {
                temp=traversal.front();
                traversal.pop();
                i=temp.first;j=temp.second;
                if(i!=0&&grid[i-1][j]==0&&visited[i-1][j]!=1&&feasibility[make_pair(i-1,j)]==numofones)
                {
                    traversal.push(make_pair(i-1,j));
                    sumoflocaldist[make_pair(i-1,j)]=sumoflocaldist[temp]+1;
                    sumofdist[make_pair(i-1,j)]+=sumoflocaldist[make_pair(i-1,j)];
                    feasibility[make_pair(i-1,j)]+=1;
                    visited[i-1][j]=1;
                }
                if(i!=m-1&&grid[i+1][j]==0&&visited[i+1][j]!=1&&feasibility[make_pair(i+1,j)]==numofones)
                {
                    traversal.push(make_pair(i+1,j));
                    sumoflocaldist[make_pair(i+1,j)]=sumoflocaldist[temp]+1;
                    sumofdist[make_pair(i+1,j)]+=sumoflocaldist[make_pair(i+1,j)];
                    feasibility[make_pair(i+1,j)]+=1;
                    visited[i+1][j]=1;
                }
                if(j!=0&&grid[i][j-1]==0&&visited[i][j-1]!=1&&feasibility[make_pair(i,j-1)]==numofones)
                {
                    traversal.push(make_pair(i,j-1));
                    sumoflocaldist[make_pair(i,j-1)]=sumoflocaldist[temp]+1;
                    sumofdist[make_pair(i,j-1)]+=sumoflocaldist[make_pair(i,j-1)];
                    feasibility[make_pair(i,j-1)]+=1;
                    visited[i][j-1]=1;
                }
                if(j!=n-1&&grid[i][j+1]==0&&visited[i][j+1]!=1&&feasibility[make_pair(i,j+1)]==numofones)
                {
                    traversal.push(make_pair(i,j+1));
                    sumoflocaldist[make_pair(i,j+1)]=sumoflocaldist[temp]+1;
                    sumofdist[make_pair(i,j+1)]+=sumoflocaldist[make_pair(i,j+1)];
                    feasibility[make_pair(i,j+1)]+=1;
                    visited[i][j+1]=1;
                }
            }
        }
        
        int shortestDistance(vector<vector<int>>& grid) 
        {
            map <pair<int,int>,int> sumofdist;
            map <pair<int,int>,int> feasibility;
            pair<int,int> temp;
            int i,j,m=grid.size(),min=INT_MAX,n,numofones=0;
            if(m!=0)
                n=grid[0].size();
            else return -1;
            
            for(i=0;i<m;i++)
            {
                for(j=0;j<n;j++)
                {
                    if(grid[i][j]==1)
                    {
                        shortestpathtraversal(i,j,m,n,sumofdist,grid,feasibility,numofones);
                        numofones++;
                    }
                }
            }
            
            for(i=0;i<m;i++)
            {
                for(j=0;j<n;j++)
                {
                    if(grid[i][j]==0)
                    {
                        temp=make_pair(i,j);
                        if(sumofdist.find(temp)!=sumofdist.end()&&feasibility[temp]==numofones&&sumofdist[temp]<min)
                            min=sumofdist[temp];
                    }
                }
            }
            
            return (min==INT_MAX)?-1:min;
        }
    
    

    };


Log in to reply
 

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