934. Shortest Bridge

This is the problem through which we can understand how dfs and bfs work in any algorithm whether it is graphs, trees or anyone.

In this problem there are two islands (islands are a combination of 1's and water is represented by 0's ), we have to connect these two islands, so we need to convert 0's to 1's, so we have to find the minimum number of zeros, we have to reverse to make it land.

for the first island, we will use DFS, and store all the zeros that are connected to 1's in the queue.

then after this we will use bfs technique and try to find the path closest to the second island as soon as we get the closest path we will return the ans.

class Solution {
public:

    int dr[4]={-1,0,1,0};
    int dc[4]={0,1,0,-1};

    void dfs(int i,int j,vector<vector<int>>& grid,queue <pair<pair<int,int>,int>>& q)
    {
        int n=grid.size();

        grid[i][j]=2;

        int cnt=0;

        for(int p=0;p<4;p++)
        {
            int r = dr[p]+i;
            int c = dc[p]+j;

            if(r>=0 && r<n && c>=0 && c<n && grid[r][c]==0)
            {
                grid[r][c]=2;
                q.push({{r,c},cnt});
            }
            else
            if(r>=0 && r<n && c>=0 && c<n && grid[r][c]==1)
            {
                dfs(r,c,grid,q);
            }

        }


    }

    int shortestBridge(vector<vector<int>>& grid) 
    {
        int n=grid.size();
        bool f=false;

        queue<pair<pair<int,int>,int>> q;

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    dfs(i,j,grid,q);
                    f=true;
                    break;
                }
            }

            if(f)
            {
                break;
            }
        }

        int ans=INT_MAX;

        while(!q.empty())
        {
            int i=q.front().first.first;
            int j=q.front().first.second;
            int c=q.front().second;
            q.pop();

            for(int k=0;k<4;k++)
            {
                int row=dr[k]+i;
                int col=dc[k]+j;

                if(row>=0 && row<n && col>=0 && col<n)
                {
                    if(grid[row][col]==1)
                    {
                        ans=min(ans,c+1);
                    }

                    if(grid[row][col]==0)
                    {
                        grid[row][col]=2;
                        q.push({{row,col},c+1});
                    }
                }
            }
        }

        return ans;

    }
};