Magical Labyrinth#7092
The magical labyrinth is represented as a rectangular grid of rows and columns, where 0 < H < 100, 0 < W < 100. Each cell in this grid contains either a zero or a one. Zeros represent free cells, and ones represent walls. The labyrinth is magical because the contents of its cells change every second. In the first second, all the cells contain ones. Thereafter, the contents of each cell change with a specific period for that cell: for the first (a-1) seconds, the cell contains , the next second it contains , then the cycle repeats (again (a-1) seconds of , one second of , etc). Each cell has its own value (1 < a < 24).
A path in the labyrinth is a sequence of cells, each of which contains a zero, and every two consecutive cells in the sequence share a side.
Your task is to find the smallest positive for which, during the -th second, the following conditions are satisfied:
The cells and (H, W) both contain zeros.
There exists a path in the labyrinth connecting these two cells.
The first line contains the natural numbers and .
Each of the following lines contains numbers: the -th number in the -th row gives the period for the cell in the -th column and -th row.
The output should consist of a single integer: the required . If no such exists, output zero.
Note: In example 3, the contents of the magical labyrinth change as follows:
Example 1