Problem 1401 --算法实现题 5-12 罗密欧与朱丽叶的迷宫问题

1401: 算法实现题 5-12 罗密欧与朱丽叶的迷宫问题

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $5$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 回溯

Description

罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个 m×n 的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这 m×n 个房间中有一些房间是封闭的，不允许任何人进入。

在迷宫中任何位置均可沿 8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。


«算法设计：
对于给定的罗密欧与朱丽叶的迷宫，计算罗密欧通向朱丽叶的所有最少转弯道路。

Input

输入第一行有 3 个正整数 n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的 k 行中，每行 2 个正整数，表示被封闭的房间所在的行号和列号。最后的 2 行，每行也有 2 个正整数，分别表示罗密欧所处的方格(p，q)和朱丽叶所处的方格(r，s)

Output

将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路输出。文件的第一行是最少转弯次数。文件的第 2 行是不同的最少转弯道路数。
接下来的 n行每行 m个数， 表示迷宫的一条最少转弯道路。 A[i][j]=k表示第 k步到达方格(i,j)；A[i][j]=-1 表示方格(i,j)是封闭的。
如果罗密欧无法通向朱丽叶则输出“No Solution!”。

Sample Input复制

3 4 2
1 2
3 4
1 1
2 2

Sample Output复制

6
7
1 -1 9 8
2 10 6 7
3 4 5 -1

推荐代码 查看1401 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 sqrjy 607954 2020-07-20 20:41:36

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛