Problem1381--선학이의 보물 찾기 - EZ

1381: 선학이의 보물 찾기 - EZ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

미로에는 여러 개의 보물이 존재한다. 선학이는 이 보물을 모두 찾으려고 한다.

보물은 소문자와 대문자로 존재하는데,
소문자 보물은 최소 1kg, 대문자 보물은 최소 100kg의 보물이며 보물의 무게는 알파벳 순으로 늘어난다.
예를 들어, a는 1kg, b는 2kg, A는 100kg, B는 101kg의 보물이다.

미로의 테두리는 모두 벽으로 둘러싸여 있다.

선학이는 상, 하, 좌, 우로만 이동할 수 있다.

얻을 수 있는 보물의 무게와 선학이와 보물간의 최소 거리의 합을 출력하자.

Input

미로의 개수 : 0 < testcase <= 10

미로의 세로, 가로 길이 : 4 <= h, w <= 100

미로의 벽은 1, 길은 공백, 선학이의 위치는 0, 보물은 알파벳으로 입력된다.

Output

보물의 무게, 보물까지 거리의 합
얻을 수 있는 보물이 없다면 "No treasure."을 출력하자.
각 testcase 사이에는 공백을 출력한다.

Sample Input Copy 

3
4 4
1111
1a01
1 11
1111
4 5
11111
1B101
1a1 1
11111
10 10
1111111111
1 a  b   1
1 111111 1
1 11 a A 1
1b  B111 1
11 11   C1
1  B  1 11
1 11111 11
1a  0   A1
1111111111

Sample Output Copy 

weight: 1
distance: 1

No treasure.

weight: 511
distance: 89

HINT

easy문제 보다 EZ 하다




* 한 지점으로 가는 최적의 경로를 찾자

Source/Category

20233115 
[Submit] [Status]