ACM的问题
发布网友
发布时间：2022-04-26 18:26
共1个回答
热心网友
时间：2023-10-20 22:57
时间*：2000/1000毫秒(java/其它) 内存*:65536/32768 K(java/其它)
所有提交次数:1694，被接收的提交次数:504
问题描述
一只狗狗在一个古代迷宫中找到一个骨头，使他非常兴奋。然而，当他捡起骨头后，迷宫开始
震动，而且狗狗发现地面在下陷。他意识到骨头是一个陷阱，他绝望地试图逃出迷宫
这个迷宫是一个N*M格的矩形。迷宫有一个门。在开始门是关着的，但可以在第T秒钟被打开
一会儿（小于1秒）。所以狗狗必须在第T秒钟前到达门前。狗狗每秒只能向相邻的格子移动1
格。每走一格，他走过着的前一个格子都会下沉，他也不能在任何一个格子上停留超过1秒。
可怜的狗狗能够活下来吗？平帮帮他
输入：
输入包括几个测试用例。每个测试的第一行是Int型N,M和T (1 < N, M < 7; 0 < T < 50),代表迷宫的长宽和门开的时间.后面的N行代表迷宫的布局，每行包括M个符号。符号的意思如下：
'X':代表墙壁，狗狗不能通过
'S':代表狗狗的起始点
'D':代表门
'.':代表没有走过的格子
输入由3个'0'结束。这个不需要处理
输出：
对于每个测试，打印'YES'表示狗狗能够生还，或者就打印'NO'
样例输入
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
样例输出
NO
YES
你的分数给的实在太少了,不过还是给你讲讲我的思路吧~~
如果你看懂了题意,那么画个图,你就会发现问题是一个典型的迷宫求解的问题.
摘引清华大学网络课程 —— 数据结构得内容:
1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；
2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；
3．所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。
显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。由此，求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝"下一位置"探索；若当前位置"不可通"，则应顺着"来的方向"退回到"前一通道块"，然后朝着除"来向"之外的其他方向继续探索；若该通道块的四周四个方块均"不可通"，则应从"当前路径"上删除该通道块。
写这个程序需要有一定的C语言水平，Java有没有什么简便的方法 我还不清楚。
