【NOIP模拟赛】水灾

2014年6月1日1,5510

http://218.5.5.242:9018/JudgeOnline/problem.php?id=1452

题目描述

大雨应经下了几天雨,却还是没有停的样子。土豪CCY刚从外地赚完1e元回来,知道不久除了自己别墅,其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示,地图上有五种符号:“. * X D S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,CCY和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动,而洪水将会在CCY移动之后把相邻的没有的土地淹没(从已淹没的土地)。
求CCY回到别墅的最少时间。如果聪哥回不了家,就很可能会被淹死,那么他就要膜拜黄金大神涨RP来呼叫直升飞机,所以输出“ORZ hzwer!!!”。

输入

输入的第一行是两个整数N和M(N,M<=50)。
接下来是一个N行M列的字符矩阵,表示ccy所在城市的地图。

输出

输出仅有一个整数,为ccy回到别墅需要的最少时间。如果无解输出-1。

样例输入

3 3 D.* … .S.

样例输出

3

题解

先bfs出每个点被水淹没的时间,然后再次bfs