407135: GYM102697 106 Geiger Counter

Geiger Counter

You're in a large maze, and unfortunately the maze is filled with differing amounts of uranium ore, which could potentially expose you to dangerous amounts of radioactivity. Luckily, you have brought your trusty Geiger Counter with you, so you can measure the radioactivity of any given part of the maze in counts per minute (CPM).

You start at the top left corner of the maze, and you are trying to travel to the bottom of the maze. For any path through the maze, its radioactivity value is defined as the maximum CPM across all cell in the maze that you travel through on the path. Your task is to find the path through the maze with the lowest radioactivity value, in other words, find the highest CPM you have to expose yourself to if you travel on the optimal path.

You're allowed to move in any direction (except diagonally), and you can visit the same cell twice (although it is never necessary to).

Note that since the constraints on the size of the maze are fairly large, a brute force (complete search) solution that tries all possible paths,will not work.

The first line of input contains two space-separated positive integers $$$n$$$ and $$$m$$$: the number of rows and columns in the maze, respectively. $$$n$$$ and $$$m$$$ will be less than 100. The next $$$n$$$ lines each contain a string containing $$$m$$$ digits (between 0 and 9), representing the radioactivity of each space in the maze in CPM.

Output a single positive integer: the maximum amount of radioactivity that you have to expose yourself to, if you travel optimally through the maze and minimize this value.

6 8
13567657
24903578
83107213
98829363
25511282
39108443

4

6 5
89888
88898
99998
88888
89999
88888

8

If you aren't sure where to start, try thinking of the maze as a graph.

Also, you should add these two lines to the top of your code if you're going to use recursion in your solution and you're coding in Python:

import sys

sys.setrecursionlimit(20000)