#6096. 小可爱先生的约会 I:惊吓迷宫 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ykj12

题目描述

纯纯dfs模板加一点小改动的极其简单的练手速的题目

n<=10的数据已经很银杏了!!


众所周知,小可爱先生不仅拥有俊俏的容颜,还拥有惊人的才华:liaomei。

是的,你没有听错。就在今天晚上,小可爱先生又要去约会了,可是他貌似遇到了麻烦,请求同样帅气(美丽)的…你…的同学(你的闺蜜/基友)去救他,还要求你为他想出办法,好让你的好盆友和小可爱先生的惊吓度尽量低,身为s*,你不得不接受这次委托。

小可爱先生和你的好盆友将会从(1,1)走到(n,n)

但是…你有这么善良吗?很明显没有,因为你的好盆友平时就和小可爱先生一起欺负你,所以,你编写了一个程序,计算如何安排计划才可以使他们惊吓度最高,但不至于趋势。

接下来,就是你…的手,表演的时候了!


现在,给予你小可爱先生约会的n*n平面地图,“.”表示可以通行,“#”表示不能通行,走过的格子会立马塌陷下去,有些格子会给出惊吓度s(有惊吓度的格子说明一定可以走),说明这个格子一旦走上去,就会出现惊吓度为s的张恩博,这时他们俩就会受到s的惊吓,当一次惊吓超过了其中一人所能承受的惊吓度,那个人就会趋势,另一个人也会因为同伴的趋势而趋势。

但你安排的路要是他们累计所受到的惊吓度最高,但s不了。

最后输出所需的步数还有累计最大的惊吓度,如果他们必s无疑,则输出“Oh,dead...Well,that's great.”


温馨提示(必看!):

1.走过的地方不能再走了。

2.两个人必须一起走,不能分开。

3.答案路径要求是最高惊吓度中的最短路径。

输入格式

第一行n

接下来n行,每行n个数,代表小可爱先生约会地点的n*n平面图。

然接下来一行是两个整数,s1,s2代表小可爱先生和你的好盆友所能承受的最大的惊吓度。

输出格式

你不能保证他们一定能活着。

如果他们回来了,请在第一行输出要走多少步才能到,第二行一个整数,代表他们所受到的惊吓值累积。

如果不能回来,请输出“Oh,dead...Well,that's great.”。

样例

样例输入 1

5
..#..
.1.35
##.#.
.#2.#
..#22
2 2

样例输出 1

8
7

样例输入 2

5
..#..
..2..
.#.2.
.##..
..#42
3 2

样例输出 2

8
6

样例输入 3

5
..#..
..3..
.#.2.
.##..
..#42
3 2

样例输出 3

Oh,dead...Well,that's great.

数据范围与提示

1<=n<10

1<=s,s1,s2<=9

样例编号| 说明 | 备注


#1 | 测试点1样例 | 已做


#2 | 测试点3样例 | 已做


#3 | n=1 && 可以走到 && 无惊吓 | 已做


#4 | n=3 && 可以走到 && 无惊吓 | 已做


#5 | n=3 && 可以走到 | 已做


#6 | n=5 && 只有一条路可走 &&可以走到 &&无惊吓 | 已做


#7 | n=5 && 可以走到 | 已做


#8 | n=8 && 不可以走到 | 已做


#9 | n=9 && 可以走到 &&无惊吓 | 已做


#10 | n=9 &&可以走到 | 已做


时间/内存限制:所有测试点1000ms,所有测试点内存限制128mb。