QAQ和迷宫

TimeLimit: 2000/1000 MS (Java/Others) MemoryLimit: 32768/32768 K (Java/Others)

64-bit integer IO format:%I64d

未提交 | 登录后收藏 | 已有3人收藏了本题

Problem Description

QAQ被围困在一个神奇的迷宫里，迷宫里有一些墙不能行走，但是迷宫里有一些墙已经很脆弱了，可以直接拆掉，但是拆一面墙必须花费d的时间，那么QAQ要逃离这个迷宫至少需要多少时间？

Input

输入的第一行是t表示测试数据的组数，每组格式如下
1. 第一行是三个整数 h, w (3 <= h;w <= 500), 和 d (0 <= d <= 50), 地图的高度和宽度，以及拆掉一格可以拆的墙的时间
2.然后是h行w列的地图，地图内容如下
―"S"表示出发点
―"."表示平地，走过需要花费1的时间
―"#"表示不能拆的墙，不能走
―"@"表示可以拆掉的墙，可以花费d的时间拆掉
全地图被不能拆的墙（也就是"#"）包围，只有一个出口。

Output

每组测试数据输出一个整数，表示走出地图所需要的最短时间。

QAQ教你广搜进阶
一般的广搜是将可行状态加入容器Q，然后每次取出最先进入Q的状态进行扩展，然后把扩展的状态依次加入Q。
而对于每个状态的权值不同的情况下，不应该是从Q拿出最先进入的状态，而是取出当前距离开始点最近的状态进行扩展。
这样的话，每次取出的状态就是依次递增的状态了。

SampleInput

3
6 5 7
#####
#S..#
#@#.#
#...#
#@###
#.###
4 5 3
#####
#S#.#
#@..#
###@#
3 3 3
###
#S#
#@#

SampleOutput

16
11
5

Submit

题目统计信息详细


总AC数	105
通过人数	69
尝试人数	76
总提交量	258
AC率	26.74%

标签——1676

name	rating
广度优先搜索	42986
优先队列	26395
基础	3620
启发式搜索	1457

AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签

出处

2015暑假培训结业赛（下半场）

QAQ和迷宫

T^T Online Judge