There is an NxM rectangular island that is partitioned into a grid of square cells. The island is surrounded by the Pacific Ocean and the Atlantic Ocean. The Pacific ocean touches the island at the top and left edge, whereas the Atlantic Ocean touches the island at the bottom and right edge. The island receives a significant amount of rain. The water can flow from the current cell to the neighboring cell directly north, south, east, or west only when the height of the neighboring cell is lesser than or equal to the height of the current cell. Your task is to find the list of all the coordinates from which water can flow to both the oceans.

There are seven coordinates through which the water can flow to both the oceans.

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());
}

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.

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.