UC知道翻译啊北大ACM1878
来源：百度知道 编辑：UC知道 时间：2024/06/21 23:23:22
题目来源：http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1878 （No.1878）
有意者请登录这个链接帮我翻译一下全文，最好是计算机人员且英语好的。
谢谢，奖20分，答得好会追加分！急！非诚勿扰
请不要用软件翻译的答案给我，如果是那样我就不会提问了！
貌似上面的那个链接不行？请点下这个http://acm.pku.edu.cn/JudgeOnline/problem?id=1878
有意者请登录这个链接帮我翻译一下全文，最好是计算机人员且英语好的。
谢谢，奖20分，答得好会追加分！急！非诚勿扰
请不要用软件翻译的答案给我，如果是那样我就不会提问了！
貌似上面的那个链接不行？请点下这个http://acm.pku.edu.cn/JudgeOnline/problem?id=1878
搞ACM不读题目想死啊。为了分，我还是搞了。
JB讨厌爬山。但是他喜欢骑车四处去，而且必须是走最可能短的道路去。幸运的是，有一个好消息，他住的地方greedhill，上面的山路是严格按照矩形网格分布的。东西走向是路，南北走向是径。而且没两个相邻交点的距离是一样的。坏消息是greedhill非常陡峭，和许多单向路径。
jill跟从以下3个规则走：
1.不走两个海拔相差超过10的路
2.单向路从不反方向行走
3.沿最短路径走
你要编程帮他找到一条最短路
输入数据：
先输入两个数字n，m；n是东西走向的路得树木，m是南北走向的径的树数目。
1<=n,m<=20
然后，是一个n*m的数字矩阵，分别代表网格上的点的海拔高度。
再然后是每行4个数字，a，b，c，d，代表（a,b）到（c,d）存在一条单向路径
直到输入4个0结束
再然后是询问要求。
每行4个数字，a，b，c，d，jb想从（a,b）到（c,d）。
直到输入4个0结束
输出：
对于每个询问要求，
如果存在一条最短路，就按格式输出最短路，如果存在多条，则随便输出一条就可以。如果，起点和终点相等按照第二个例子输出，如果路径不存在按照第三个样例输出。
（其实，可以将东西看做X坐标，南北看作Y坐标，然后，对于所有的单向路径，如果两端的海拔大于10就删除 那条边，这样就是一个普通的最短路问题了，相当水的）