/*
方格数组，高9，宽12。数字0代表空缺位置，其他数字代表
每种图像块，同数字代表同种图像块，规定头尾数组所有元
素只能为0，各数组首尾元素只能为0，以构成一个矩形环绕
空位。用表达式map_ary[0~9][0~12]，可以访问这个矩阵的
所有元素。
*/ var map_ary:Array = Array();
//// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]; map_ary[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; map_ary[1] = [0, 1, 3, 4, 7, 7, 8, 9, 1, 6, 6, 2, 0]; map_ary[2] = [0, 3, 5, 6, 8, 8, 9, 2, 5, 7, 0, 7, 0]; map_ary[3] = [0, 4, 2, 6, 7, 5, 4, 3, 0, 0, 0, 2, 0]; map_ary[4] = [0, 7, 5, 9, 3, 8, 0, 8, 0, 5, 4, 5, 0]; map_ary[5] = [0, 5, 3, 4, 0, 0, 7, 5, 4, 2, 4, 2, 0]; map_ary[6] = [0, 1, 0, 3, 6, 0, 0, 6, 2, 4, 5, 6, 0]; map_ary[7] = [0, 6, 0, 0, 0, 7, 0, 4, 3, 8, 9, 4, 0]; map_ary[8] = [0, 2, 5, 6, 7, 4, 3, 9, 7, 9, 8, 1, 0]; map_ary[9] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; /*
排序方法函数，用于Array.sort()方法的调用。编写方法是
function 函数名(第一个元素，第二个元素):Number{如果第一个元素和第二个元素不换位置则返回-1;否则返回1;如果相等就返回0}
使用：数组名.sort(函数名);
下面的这个函数把数组元素的长度作为排序的依据，a.length大于b.length则换位。从而按照此方法排序后的数组是以元素长度升序排列的。
但首先必须确认从数组中取出的的元素具有.length属性，即元素要属于Array或者String,所以被排序的数组是一个嵌套数组。
因为路径集在算法构思时被定义为一个嵌套数组，它的元素是一条条路径，而路径由一个个点组成，一个点由两个坐标组成。
如：paths=[[[1,1],[1,2],[1,3]],[[2,1],[2,2]]]
paths.length的值为2,即包含两条路径
paths[0].length的值为3，即第一条路径的长度是3，也即第一条路径包含3个点
[1,1],[1,2],[1,3]。
如果要访问到最低层元素可以用类似表达式：paths[0][0][0] 值为1，意为第一条路径的第一个点的第一个坐标。
paths.sort(byLength)后较深层数据顺序不变，只改变paths第一层数据即路径的顺序。结果为：[[[2,1],[2,2]],[[1,1],[1,2],[1,3]]]
*/ function byLength(a:Array, b:Array):Number {
if (a.length>b.length) {
return 1;
} else if (a.length<b.length) {
return -1;
} else {
return 0;
}
}
/*
遍历序列建立函数，建立一个从v1到v2值中间向两边扩展的序列，以确保遍历从可能出现最短路径的位置开始。
如有一个数列8,6,4,2,0,1,3,5,7,9 现假设要从0的位置开始扩展，得到的数列为0,1,2,3,4,5,6,7,8,9。
现在反过来，原来数列是0,1,2,...,vmax，用(v1+v2)/2作为开始位置。
如：create_sequence(1,8,9)得到的数组是：4,5,3,6,2,7,1,8,0,9。
*/ function create_sequence(v1:Number, v2:Number, vmax:Number):Array {
var sequence:Array = Array();
var tmp_ary:Array = Array();
for (var j = 0; j<=vmax; j++) {
sequence.push(j);
}
var i = int((v1+v2)/2);
for (j=0; j vmax-i ? i : vmax-i); j++) {
if (j == 0) {
tmp_ary.push(sequence[i]);
} else {
if (sequence[i+j] != undefined) {
tmp_ary.push(sequence[i+j]);
}
if (sequence[i-j] != undefined) {
tmp_ary.push(sequence[i-j]);
}
}
}
return tmp_ary;
}
/*
下面函数的作用是判断路径是否被阻断(是否不全为0)，如果被阻断则返回值true，主函数将继续下一个搜索。
a是个数组用来接收一段路径。其他四个数字是例外的点，因为被判断的两个图块不可能是空缺的，但是
路径的两端包含着这两个点，传递这四个参数的目的是把它们当作是通的。
*/ function ary_isBlocked(a:Array, x1:Number, y1:Number, x2:Number, y2:Number):Boolean { for (var m = 0; m<a.length; m++) {
if (map_ary[a[m][0]][a[m][1]] != 0) {
if ((a[m][0] == x1 && a[m][1] == y1) || (a[m][0] == x2 && a[m][1] == y2)) {
} else {
return true;
}
}
}
return false;
}
/*
下面函数的作用是判断一个点是否被阻断(是否不为0)，如果被阻断则返回值true，主函数将继续下一个搜索。
*/ function pot_isBlocked(xi:Number, yi:Number, x1:Number, y1:Number, x2:Number, y2:Number):Boolean {
if ((xi == x1 && yi == y1) || (xi == x2 && yi == y2)) {
return false;
}
if (map_ary[xi][yi] != 0) {
return true;
} else {
return false;
}
}
/*
路径寻求函数，前四个参数用来传递两点的坐标，最后一个参数控制是否求得所有路径。该函数的返回值类型为数组类型，
详细内部结构见上述。
*/
function paths(x1:Number, y1:Number, x2:Number, y2:Number, xmax:Number, ymax:Number, isAll:Boolean):Array {
//首先判断两点的图像是否一致 if (map_ary[x1][y1] == map_ary[x2][y2]) {
/*
定义内部变量：
p1_x_ary与p2_x_ary存储两点在纵向的两条平行轨道
p1_y_ary与p2_y_ary存储两点在横向的两条平行轨道
px_ary存储架在两平行纵向轨道上的滑竿
py_ary存储架在两平行横向轨道上的滑竿
tmp_ary是一个临时数组，存储临时性的数组数据
points_ary点集数组，每次遍历如果圆满完成，将形成一条通路径
paths_ary路径集数组，每次遍历如果圆满完成，保存points_ary的路径 sequence_ary存储遍历序列
blocked标记性变量，当按点判断滑竿是否被阻断时，如果遇到一点不通则跳出(break)当前循环
并置blocked的值为true，以便再继续(continue)下次遍历 */ var p1_x_ary:Array = Array();
var p1_y_ary:Array = Array();
var p2_x_ary:Array = Array();
var p2_y_ary:Array = Array();
var px_ary:Array = Array();
var py_ary:Array = Array();
var tmp_ary:Array = Array();
var points_ary:Array = Array();
var paths_ary:Array = Array();
var sequence_ary:Array = Array();
var blocked:Boolean; /* 创建轨道和滑竿 Array.push(表达式)方法：把整个表达式的值作为一个元素加入到数组尾部。
请注意与Array.concat()方法不同之处，见下述。
*/ for (var m = 0; m<=xmax; m++) {
p1_x_ary.push([m, y1]);
}
for (m=0; m<=ymax; m++) {
p1_y_ary.push([x1, m]);
}
for (m=0; m<=xmax; m++) {
p2_x_ary.push([m, y2]);
}
for (m=0; m<=ymax; m++) {
p2_y_ary.push([x2, m]);
}
for (m=(y1<y2 ? y1 : y2); m y1 ? y2 : y1); m++) {
px_ary.push([0, m]);
}
for (m=(x1<x2 ? x1 : x2); m x1 ? x2 : x1); m++) {
py_ary.push([m, 0]);
}
/*
如果两点不在同一列时启动px_ary纵向的遍历
*/ if (y1 != y2) {
/*
首先建立遍历序列
*/ sequence_ary = create_sequence(x1, x2, xmax); for (var i = 0; i<=xmax; i++) { m = sequence_ary[i];
if (m<x1) {
/*
Array.slice(a, b)方法，返回从数组下标为a到数组下标为b-1的元素所构成的新数组。
*/ tmp_ary = p1_x_ary.slice(m+1, x1+1);
/*
Array.reverse()方法，把目标数组的元素位置倒置
*/ tmp_ary.reverse();
if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) {
/*
如果tmp_ary被阻断则给points_ary
点集数组重新分布空间，把原来的数据丢弃。
continue会把程序运行指针转回到
循环开始处，下面的语句不会被执行，开始下一次的循环。
continue只会与其最贴近的循环体
起作用
*/ points_ary = new Array();
continue;
}
/*
Array.concat(a:Array)将数组a的元素添加到目
标数组的末尾。
如果a=[1,2];b=[[3,4],[5,6]];b.concat(a);b为
[[3,4],[5,6],1,2];
如果a=[[1,2]];b=[[3,4],[5,6]];b.concat(a);b为
[[3,4],[5,6],[1,2]];
请注意与Array.push()方法不同之处，见上述。
*/
points_ary = points_ary.concat(tmp_ary);
} else if (m>x1) {
tmp_ary = p1_x_ary.slice(x1, m);
if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) {
points_ary = new Array();
continue;
}
points_ary = points_ary.concat(tmp_ary);
}
if (y1<y2) {
for (var n = 0; n<px_ary.length; n++) {
if (pot_isBlocked(m, px_ary[n][1], x1,
y1, x2, y2)) {
points_ary = new Array();
blocked = true;
/*
按点判断是否被阻断，如果
遇到阻断则用break终止
此次按点循环判断，并置
blocked标志为true，在跳
出循环后继续滑杆的下一
次遍历。break用来终止循环；
break只会与其最贴近的循
环体起作用。
*/ break;
} else {
blocked = false;
}
points_ary = points_ary.concat([[m,
px_ary[n][1]]]);
}
y1, x2, y2)) {
px_ary[n][1]]]);
if (blocked) { continue; } } else { for (n=px_ary.length-1; n>=0; n--) { if (pot_isBlocked(m, px_ary[n][1], x1, points_ary = new Array(); blocked = true; break; } else { blocked = false; } points_ary = points_ary.concat([[m, } if (blocked) { continue; } } if (m<x2) { tmp_ary = p2_x_ary.slice(m+1, x2+1); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } else if (m>x2) { tmp_ary = p2_x_ary.slice(x2, m); tmp_ary.reverse(); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary);
}
paths_ary.push(points_ary); points_ary = new Array(); if (isAll) { } else {
break; }
}
}
y1, x2, y2)) {
/* 如果两点不在同一列时启动py_ary横向的遍历 */ if (x1 != x2) { sequence_ary = create_sequence(y1, y2, ymax); for (i=0; i<=ymax; i++) { m = sequence_ary[i]; if (m<y1) { tmp_ary = p1_y_ary.slice(m+1, y1+1); tmp_ary.reverse(); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } else if (m>y1) { tmp_ary = p1_y_ary.slice(y1, m); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } else if (y1 != y2) { continue; } if (x1<x2) { for (n=0; n<py_ary.length; n++) { if (pot_isBlocked(py_ary[n][0], m, x1, points_ary = new Array(); blocked = true; break; } else { blocked = false; } points_ary =
points_ary.concat([[py_ary[n][0], m]]);
}
if (blocked) {
continue;
}
} else {
for (n=py_ary.length-1; n>=0; n--) {
if (pot_isBlocked(py_ary[n][0], m, x1, y1, x2, y2)) {
points_ary = new Array(); blocked = true;
break;
} else {
blocked = false;
}
points_ary
points_ary.concat([[py_ary[n][0], m]]);
}
if (blocked) {
continue;
}
}
if (m<y2) {
tmp_ary = p2_y_ary.slice(m+1, y2+1);
if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array();
continue;
}
points_ary = points_ary.concat(tmp_ary); } else if (m>y2) {
tmp_ary = p2_y_ary.slice(y2, m);
tmp_ary.reverse();
if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array();
continue;
}
points_ary = points_ary.concat(tmp_ary); } else if (y1 != y2) {
points_ary = new Array();
continue;
}
paths_ary.push(points_ary);
points_ary = new Array();
if (isAll) { =
} else {
break;
}
}
}
if (isAll) {
} else {
/*
如果isAll为false，即只要求得最短路径。
}
}
将paths_ary进行排序以便确保最短路径在前面 */ paths_ary.sort(byLength); /* 返回排序后的第一条路经 */ return [paths_ary[0]] } return paths_ary;
班级：物联网1201姓名：刘潇学号：1030612129一、实验内容：这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题…
算法学习心得:算法这个词是在我在大学第一次C语言课上听到的，当时老师讲的是程序=算法+数据结构，算法是一个程序的灵魂。当时我什么也…
第四章查找匹配41有序数组的查找题目描述给定一个有序的数组查找某个数是否在数组中请编程实现分析与解法一看到数组本身已经有序我想你可…
算法设计与分析课程的心得体会以最少的成本最快的速度最好的质量开发出合适各种各样应用需求的软件必须遵循软件工程的原则设计出高效率的程…
方格数组高9宽12数字0代表空缺位置其他数字代表每种图像块同数字代表同种图像块规定头尾数组所有元素只能为0各数组首尾元素只能为0以…
算法学习心得:算法这个词是在我在大学第一次C语言课上听到的，当时老师讲的是程序=算法+数据结构，算法是一个程序的灵魂。当时我什么也…
班级：物联网1201姓名：刘潇学号：1030612129一、实验内容：这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题…
课程设计心得体会姓名：曾辉学号;0804012041班级：08计本（2）课程设计是计算机科学与技术专业学生的集中实践性环节之一，是…
课程设计的心得体会姓名：何云龙学号：0804012022班级：08计科（2）班“数据结构与算法课程设计”是计算机科学与技术专业学生…
C课程设计心得感想课程设计是培养学生综合运用所学知识发现提出分析和解决实际问题锻炼实践能力的重要环节是对学生实际工作能力的具体训练…