| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11291 | Mouse Maze |
|
| 13701 | fruit sale |
|
Description
Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.
The maze type is shown in following figure:
S$###
$$#$$
$$$##
##$$F
it consists of S (starting point), #(walls), $(road) and F (final point).
In above case, it needs 7 steps from S to F as following figure,
S$###
$$#$$
$$$##
##$$F
and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.
If there is no way from S to F, then print -1.
Input
The first line has an integer N(1<=N<=10^6), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.
The following R lines, each containing C characters, specify the elements of the maze.
Output
Print out the least steps for each case, and there is a new line character at the end of each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A new supermarket has opened in Bikini Bottom!
Since the supermarket has just opened, the fruit section is having a sale: given a basket, you can fill it with any kind and any amount of fruit. No matter what you have chosen, the whole basket of fruit costs 10 dollars, as long as the basket can bear the weight.
Squidward has made Spongebob and Patrick buy some fruit in this sale for him, please help them figure out the maximum value they could get.
There are only n kinds of fruit left. Each of them has its weight and value. The value of the whole basket of fruit is the sum of the value of each kind of fruit. Squidward only wants to eat at most one unit for each kind of fruit.
Input
The first line contains an integer n, representing the remaining number of fruit.
The second line contains n integers w1, w2 ... wn. Represent each kind of fruit's weight per unit.
The third line contains n integers v1, v2 ... vn. Represent each kind of fruit's value per unit.
The last line contains an integer W, the maximum weight a basket could bear.
Constraints:
1 ≤ n ≤ 20
1 ≤ wi, vi, W ≤ 107, ∀i ∈ [1, n]
Output
Output the maximum value of the basket that Spongebob and Patrick could get.