The smallest path - 1
Practice
3.9 (875 votes)
Hard
Problem
34% Success 3047 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Maga gives a hard problem to Alex. And Alex couldn't solve yet. Could you help him?

The grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.

Input:
In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.

Output:
Output the most beautiful path.

Contraints:
1 <= n,m <= 1000
1 <= A[i][j] <= n*m, All of the numbers in the grid are unique.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
10 votes
Tags:
Basic ProgrammingDynamic ProgrammingAlgorithmsIntroduction to Dynamic Programming 1ImplementationBasics of Implementation
Points:30
49 votes
Tags:
AlgorithmsApprovedBinary SearchEasySearching
Points:30
4 votes
Tags:
Number TheoryPrime FactorizationEasy-MediumMathematicsSieveFactorization