Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Problem

By aro001 · Limits 1s, 512 MB

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 city? 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 answer.

Sample

InputOutput
111
101
111

11111111
11111111
11101111
11111111
Case 1: 2
Case 2: 2

    Discussion

    Statistics


    60% Solution Ratio

    subhashis_cseEarliest, 3M ago

    Sara_HasanFastest, 0.0s

    Sara_HasanLightest, 0 B

    Fazlerabbi.Shortest, 749B

    Submit

    Login to submit

    Related Contests