This page is still under construction.

Parts of this page are still being built. What you see may change.

Jinwoo's Mint Chocolate Milk

Interview

Time limit1sMemory limit512 MB

Summary
On an N x N grid with one home, at most ten milk spots, initial stamina M, and stamina gain H per drink, find the most bottles Jinwoo can drink and still return home.
Level

Medium6 of 10

Topics
Backtracking, BFS, Graph, Brute force
Solved
No attempts yet

Problem

Jinwoo is a member of the mint chocolate faction who loves mint chocolate milk. Even when things are hard, he says one bottle of mint chocolate milk fills him with energy!

Jinwoo loves mint chocolate milk so much that he moved to Mint Choco Village, an N × N two-dimensional grid, where mint chocolate milk is delivered to certain spots every morning.

When Jinwoo wakes up in the morning, he leaves home with a map of Mint Choco Village and sets out to find mint chocolate milk. His initial stamina is M. Here, stamina represents the distance Jinwoo can travel. Jinwoo can move one cell up, down, left, or right on the map, and each move reduces his stamina by 1. If Jinwoo drinks mint chocolate milk while wandering the village, his stamina increases by H, and it can rise above his initial stamina. The moment his stamina reaches 0, Jinwoo cannot move.

A situation must not arise where Jinwoo runs out of stamina in the middle of the village while searching for mint choco and cannot return home. Let us find out how many bottles of mint chocolate milk Jinwoo can drink and still return home.

Input

The first line gives the size of Mint Choco Village N, Jinwoo's initial stamina M, and the amount of stamina H gained each time he drinks mint chocolate milk, separated by spaces. N, M, and H are all natural numbers less than or equal to 10.

From the second line to the N+1-th line, the map of Mint Choco Village is given over N cells. Each cell is separated by a space, and on the map Jinwoo's home is given as 1, mint chocolate milk as 2, and empty ground as 0. There is always exactly one home for Jinwoo, and the total number of mint chocolate milk bottles delivered to the village does not exceed 10.

Output

Print the maximum number of mint chocolate milk bottles Jinwoo can drink from the time he leaves home until he returns home.

Examples2

  1. Example 1

    Input
    10 2 3
0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 2 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0
0 2 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 2 0
0 0 0 1 0 0 2 0 0 0
0 0 0 0 2 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0
    Expected output
    2

  2. Example 2

    Input
    6 8 3
0 0 1 0 0 0
0 2 0 2 0 0
0 0 0 0 0 2
0 0 0 0 0 0
2 0 0 2 2 2
0 0 2 0 0 0
    Expected output
    8