Water Flow Problem Statement
You are given a matrix 'A' of size 'N' x 'M', where each cell contains the height of water placed in that cell. Water can flow in four directions: up, down, left, and right, but only to cells with heights less than or equal to the current cell's height. The left and top boundaries of the matrix represent the Pacific Ocean, while the right and bottom boundaries represent the Atlantic Ocean.
Your task is to determine all coordinates from which water can flow to both the Pacific and Atlantic Oceans. The output should list these coordinates sorted in lexicographical order.
Input:
The first line of input contains an integer 'T', representing the number of test cases.
For each test case, the first line contains two space-separated positive integers 'N' and 'M'.
The following 'N' lines each contain 'M' space-separated integers representing the heights in matrix 'A'.
Output:
For each test case, output should begin with a positive integer 'K', denoting the number of coordinates.
The following 'K' lines should each contain one coordinate.
Example:
Input:
1
3 3
1 2 2
3 2 3
2 4 5
Output:
4
0 1
0 2
1 0
1 1
Constraints:
- 1 <= T <= 50
- 1 <= N <= 104
- 1 <= M <= 104
- 1 <= N*M <= 104
- 1 <= A[i][j] <= 109
- Time Limit: 1 sec
Note:
You do not have to print anything; implement the function as directed.
Be the first one to answer
Add answer anonymously...
Top uCertify Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app