You are responsible for testing the compressive strength of
various composite materials. You take a rectangular block,
crush it from the sides and see where it beaks. This is hard
work, and itâ€™s dirty, so you decide to write a simulator to get
yourself some help.
Computationally, you model a block as being composed of a
grid square regions of materials of various strengths. You
model the strength of a square as an integer between
$1$ and $9$. When sufficient force is applied
from the sides, the block will shatter along a fracture line. The fracture line is a path
through the squares that starts in a square along the top edge
of the block and ends in a square along the bottom edge. Among
all such paths, the fracture line is the one that minimizes the
total strength (i.e., the sum of the
strength values) of all the squares on the path. The fracture
line can travel from square to square up, down, left, right or
diagonally as it goes from the top edge to the bottom edge.
Input
Input consists of up to $200$ block descriptions. Each block
description starts with a line containing two integers,
$1 \le h \le 20$ and
$1 \le w \le 60$, giving
the height and width of the block. This is followed by
$h$ lines of $w$ digits each, where each digit is
in the range $1 \ldots 9$.
The end of all block descriptions is marked by values of zero
for $r$ and $c$.
Output
For each block, print a copy of the block with the digits
along its fracture line replaced by spaces. There will only be
one fracture line that has the minimum strength. Print a blank
line after each block.
Sample Input 1 
Sample Output 1 
3 7
2281431
2329463
7183839
7 6
517135
935519
731353
375951
575195
579573
359739
0 0

228 431
23 9463
7 83839
517 35
9355 9
73135
37595
57519
57957
3597 9
