电影系列题目之《遇见未来》 ## 题目描述 2007年，好莱坞拍摄了科幻电影《预见未来》（Next）。电影的故事情节是：魔术师克里斯•约翰逊能预知下一刻将要发生的事情；一个恐怖组织威胁要引爆核炸弹，把洛杉矶夷为平地；克里斯需要利用他的特异功能帮助FBI查出恐怖分子藏在哪里，…。 在本题中，恐怖分子藏身处用一个M×N的网格表示。网格中每一个方格可能是障碍物、可通行的方格、克里斯的起始位置或恐怖分子藏身处。从每一个方格出发，克里斯向上、下、左、右走到相邻的方格，所需的时间是1秒。克里斯能预测T秒，也就是说从当前位置出发，T秒钟能到达的方格里是否藏有恐怖分子，他都知道。现在的问题是克里斯至少需要多长时间才能找到恐怖分子的藏身处。 ## 输入描述 输入文件中包含多个测试数据。每个测试数据的格式如下：第1行为3个整数M、N和T，分别表示网格的行和列、以及克里斯能预测T秒，5≤M, N≤10，2≤T≤5；接下来有M行，每行有N个字符，这些字符可能为'#'、'.'、'S'和'D'，分别表示障碍物、可以通行的方格、克里斯的起始位置、恐怖分子藏身处，每个测试数据中只有一个'S'和'D'。测试数据一直到文件尾。 ## 输出描述 对每个测试数据，输出克里斯找到恐怖分子的藏身处所需的最少时间（注意，该时间可能为0）。如果克里斯无法到达目标位置，输出"dead"。 ## 样例输入 ```txt 5 6 3 .#..## #S...# #.##.# #.#.D# #....# 6 6 4 .#..## #..#.# #.S#.# ###.D# #....# #.#..# ``` ## 样例输出 ```txt 2 dead ```