Bob is lost in the city of Cownogor. It is a great problem for him now. People in
Cownogor speaks Cow language (For more see: https://esolangs.org/wiki/COW).
As an outsider he is not familiar with this language. So he cannot ask anyone for
direction. Moreover he lost his phone. But he knows that he can go back to his
city if he can get out of this city anyway.
Cownogor can be represented with a grid of height and width w. Each cell of the
grid represents a place of the city. Each cell is connected with all of its 8 adjacent
cells (if there) with a path. One can go from a cell to another cell in one second.
He needs gij money to visit the cell of ith row (from left) and jth column (from top).
Bob believes that straight path is the only way to success. So he follows straight
paths only and avoid all other paths. He visits a cell if it is adjacent to his current
cell and has a straight path between them. He considers a path is straight if it
connects two adjacent cells sharing at least one side.
Now he is in the cell of ith row (from left) and jth column (from top). Can you
determine the minimum time that he must travel before he can get out of this
You are given a grid. Each line contains integers gi,j (0<=gij<=9)-The cost to visit
this cell. There are no space between numbers. Bob's Current position is in the
cell which costs 0 and no other cell costs 0. Each test case except the last one is
followed by an empty line.
For each test case your output should be a line with case number followed by the
111 101 111 11111111 11111111 11101111 11111111
Case 1: 2 Case 2: 2