Waterflow Problem

Approach

In the above problem, it has been given to us that water can flow from one cell to another in four directions: up, down, right, and left only when the height of the neighboring cell is lesser than the height of the current cell. It will not be accessible if we try to find out all the points by checking whether it flows to the Pacific Ocean and the Atlantic Ocean. Instead of moving from a higher height cell to a lower one, we will move from a lower height cell to a higher one. Instead of finding points from which water can flow from the cell to the ocean, we will try to find those cells that can receive water from the ocean (Pacific/Atlantic).

Now, If we closely observe the above problem statement, it can be observed that all the cells which are in the top row (i=0) and the leftmost column (j=0) will always receive water from the Pacific Ocean.

Then we try to find out all the cells that can be accessed or to which water can flow from these points individually using a multisource BFS.

Similarly, we will do the above process for the Atlantic Ocean. All the rightmost (i=row) and the bottom-most (j=col) cells will always receive water from the Atlantic Ocean. 

Finally, the common cells that are the ones that receive water from both the Pacific and Atlantic oceans will be the answer.

Diagramatic Representation

Cells that are reachable ( receive water) from the Pacific Ocean are circled in red, while the cells that are reachable  ( receive water) from the Atlantic Ocean are circled in blue.
 

The cells which are common in both are circled in green.

Algorithm

The problem can be solved using multisource BFS traversal. The main idea is to visit or mark all the cells that can receive water from both the Pacific and Atlantic oceans separately using BFS. The cells which are visited or marked by both the oceans will formulate the result.

Steps

• Create two 2D vectors of bool type to keep a record of the visited cells by the Pacific and the Atlantic ocean individually.
• Create two queues of type pair<int, int> to store the coordinates of the matrix.
• Traverse the entire matrix and store the coordinates which are directly connected to the Pacific Ocean and the Atlantic Ocean in their respective queues.
• Perform BFS traversal on each queue individually.
• Finally, Traverse both the visited vectors and print the coordinates of those cells marked as visited in both.

Code 

#include<bits/stdc++.h>

// stores all the directions
int dir[4][2]={{0,-1}, {-1,0}, {0,1}, {1,0}};

void bfs(vector<vector<int> >& mat, queue<pair<int,int> >&q,    vector<vector<bool> > &visited, int &row, int &col){
  
      while(!q.empty()){
      int x=q.front().first;
      int y=q.front().second;
      q.pop();

      for(int i=0;i<4;i++){
        // generate new coordinates
        int newX = x + dir[i][0];
        int newY = y + dir[i][1];
        
        // check if new-coordinates are within the bounds or not
        if(newX<0 || newY<0 || newX>=row || newY>=col || visited[newX][newY]){
            continue;
        }

        // check if the new cell is at higher height from current cell
        if(mat[x][y]<=mat[newX][newY]){
            q.push({newX,newY});
            visited[newX][newY]=true;
        }
      }
  }

}

void waterFlow(vector<vector<int>> &mat, int n, int m) {

  int row=n, col=m;

  // base condition
  if(row==0) return;

  // making visited 2D vector for checking if the points touched the oceans
  vector<vector<bool> > pac_visited(row, vector<bool>(col,false));
  vector<vector<bool> > atl_visited(row, vector<bool>(col,false)); 

  // create queues
  queue<pair<int,int> > pacQ, atlQ;

  // intialise the queues
  for(int i=0;i<row;i++){
      for(int j=0;j<col;j++){

        // pacific ocean touches top & left side
        if(i==0 || j==0){
            pacQ.push({i,j});
            pac_visited[i][j]=true;
        }

        // atlantic ocean touches bottom & right
        if(i==row-1 || j==col-1){
            atlQ.push({i,j});
            atl_visited[i][j]=true;
        }
      }
  }

  // explore all the points touched by the ocean
  bfs(mat,pacQ,pac_visited,row,col);
  bfs(mat,atlQ,atl_visited,row,col); 

  // formulate the results
  for(int i=0;i<row;i++){
      for(int j=0;j<col;j++){
        // points common in both
        if(atl_visited[i][j] && pac_visited[i][j]){
            cout<<i<<" "<<j<<endl;
        }
      }
  }
}

int main(){
  vector<vector<int> > mat= { { 1, 2, 2, 3, 5 },
                          { 3, 2, 3, 4, 4 },
                          { 2, 4, 5, 3, 1 },
                          { 6, 7, 1, 4, 5 },
                          { 5, 1, 1, 2, 4 } };

  waterFlow(mat,mat.size(),mat[0].size());
}

Output

0 4
1 3
1 4
2 2
3 0
3 1
4 0

Time Complexity: O(N*M)

Auxiliary Space: O(N*M)

Check out this problem - Queue Implementation

Frequently Asked Questions

What is BFS?

BFS stands for Breadth-first search. It is a graph traversal algorithm that starts traversing the graph from the root and explores all the neighbors of the current node. 
 

What is Multisource BFS?

Multisource BFS works in the same as a regular BFS does. The only difference is that in the case of multisource bfs, multiple sources are added to the queue in the beginning.
 

What is a queue?

A queue is a linear homogenous data structure that follows a particular order in which operations are performed. A queue follows the First in First Out (FIFO) policy.

Conclusion

In this article, we have extensively discussed the Water Flow Problem in detail.

After reading about the WaterFlow Problem, are you not feeling excited to read/explore more articles on BFS? Don't worry; Coding Ninjas has you covered. To learn how to solve the water jug problem using BFS, understand the concept of flood fill algorithm, and the graph traversal techniques using bfs/DFS Algorithm. 

If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, and many more, then you should check out our Guided path column at Coding Ninjas Studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company. 

Do upvote if you find the blogs helpful.

Happy Learning!