Lexicographically Smallest Path
Given a grid of characters, find the lexicographically smallest path from the top-left cell (0,0) to the bottom-right cell (R-1, C-1). You can only move right or down. The path is represented by the sequence of characters visited, starting from the top-left and ending at the bottom-right. If multiple paths have the same lexicographically smallest sequence, choose the one with the minimum length (though all paths will have the same length R+C-1 in this problem).
Input
The first line contains two integers R and C (1 <= R, C <= 200). The next R lines each contain C characters, representing the grid.
Output
Print the lexicographically smallest path as a string.
Constraints
1 <= R, C <= 200. Grid contains only lowercase English letters.
Example 1
3 3 abc def ghi
abcfi
The path 'adg' is lexicographically smaller than 'abe', 'abf', etc. The path 'adg' leads to 'adg'. The path 'aei' leads to 'aei'. The path 'abdh' leads to 'abdh'. The path 'abdg' leads to 'abdg'. The path 'adg' is indeed the smallest.
Example 2
2 4 xzyw aqrs
xaqrs
The path 'xaqrs' is smaller than 'xzyrs'.
Hints
Similar problems
- Maximum Sum Non-Adjacent PairsMedium
- Longest Zigzag SubsequenceMedium
- Maximum Sum Increasing SubsequenceMedium
- Count Paths on a LineEasy
- Count Subsequences Summing to KEasy
- Find Minimum Depth Binary TreeMedium
More topics: Dynamic Programming problems, Graphs, BFS and DFS problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 3 abc def ghi
2 4 xzyw aqrs