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 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$.
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