高中信息技术：最少转弯教学设计

新修订高中阶段原创精品配套教材

最少转弯

教材定制 / 提高课堂效率 /内容可修改

Least turn

教师：风老师 风顺第二中学

编订：FoonShion教育

原创教学设计 Excellent Teaching Design 最少转弯

教材说明：本教学设计资料适用于高中信息技术科目 ，主要用途为帮助学生通过学习高效率的科技手段，使学生在社会生活中能通过更快解决生产、生活中的实际问题，并能严谨地思考，并能产生良好的解决方法，进而促进全面发展和提高。内容已根据教材主题进行配套式编写，可直接修改调整或者打印成为纸质版本进行教学使用。 在一个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

第 2 页 / 总 3页

原创教学设计 Excellent Teaching Design 1 1 3 7 4 3 1 4 3 5 3 7 －1 －1

样例输出： (road.out) 2 2 1 2 7 <

FoonShion教育研究中心编制

Prepared by foonshion Education Research Center

第 3 页 / 总 3页