最少转弯问题_最少转弯

高中信息技术教案 2015-07-21 网络整理 晴天

【jiaoan.jxxyjl.com--高中信息技术教案】

在一个n*m的方格通路中,去掉若干个点,如下图。其中加0的点表去掉的点。在图中,任给两点p,q,找出一条从p到q转弯最少的路径(路径中的每一步只能沿水平或垂直方向行进,去掉的点不能通过)。

输入格式:

输入的第一行为n与m(均不大于100),第二行有四个整数px,py,qx,qy分别表示p、q点的坐标,第三行开始每行有两个整数x,y,表示一个去掉的点的坐标(p、q点一定不是去掉的点)。输入文件以-1,-1表示结束,图中最左上角的b1坐标为(0,0),向下为x方向,向右为y方向。

输出格式:

输出有若干行,第一行为转弯数,第二行开始顺序输出所求的转弯最少的路径中的每一个拐点的坐标,每行表示一个点。

样例输入: (road.in)

5 8

1 1 3 7

4 3 

1 4

3 5

3 7

-1 -1

样例输出: (road.out)

2

2 1

2 7

<

本文来源:https://jiaoan.jxxyjl.com/gaozhongxinxijishujiaoan/31758.html

Copyright @ 2011-2019 教案下载网 All Rights Reserved. 版权所有

免责声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。

 站长统计