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...
uCertify Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter