Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
迷宫寻宝
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 15, Accepted users: 13
Problem 10636 : No special judgement
Problem description
   数据结构一篇关于迷宫求解的问题,我想大家一定都没有做过,今天我们坏马啃回头草。虽然很无聊,但是能做出了,尤其不看书的情况下,那就有聊的了。告诉你一个秘密,我的测试数据很水的,都是随机产生的,所以很多的答案会是无解的。

Input
  有TN个测试数据;

我会给你一个迷宫,我会将它表示成矩阵形式,其中‘#’表示墙,你是穿不过的。‘=’表示路,你当前所在的位置标记为‘Y’,你要去的地方标记为‘T’。

 第一行为TN

每个测试数据包含以下信息:

第一行:行M,列NM,N>1&&M,N<21

以下MN列的矩阵就是迷宫信息了。

Output
  你的目的是,寻找一条路径可到目的地的,如果你去不了,输出“Impossible.”,否则输出你可到目的地的最少步数(也就是要走的方格数)。你的行动方向只能是上下左右。

Sample Input
2
6 14
##===#======##
==T==###=###=#
##=#=#===#===#
====#=#=#####=
##===Y=#==##==
###=#==###=#==
4 8
==Y=##=#
==##==##
##==T=##
=#=##=##
Sample Output
6
Impossible.
Problem Source
  Chenb

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:19444 today,16242435 total, since 2010-05-07