作为“算法及实现”栏目的“抛砖引玉”之作，将自己2年多前实现的一个算法放出来。有一年IBM出了这个Java程序设计竞赛题，当时，自己花晚上时间用Java实现了。
[问题描述]:
任意给定一个正方形，将正方形的各边做n等分,并将相应各点连接成水平或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角(n,n),请用Java程序计算并输出所有可能的路径总数和具体线路.请提供相关Java源程序和n=2,3,4时的输出结果。输出结果按以下方式:
以n=1为例:
n = 1
Path1: (0,0) - (0,1) - (1,1)
Path2: (0,0) - (1,0) - (1,1)
Total = 2
[设计简介]：
共设计3个类：
AixPoint：正方形问题的低层处理类,抽象正方形问题的每个访问点信息；
AixSquare：正方形问题的核心处理类,抽象正方形算法处理过程；
AixContest：正方形问题的客户调用处理类,抽象正方形问题的应用层。
[算法源码]：
AixPoint源码：
/*******************************************************************************
* <<AIX 程序设计大赛---AIX正方形问题>> * AIXContest ver1.0 * 开发作者: 成晓旭 * 项目简述: AIX程序设计的Java程序设计"AIX正方形问题"解决方案 * 启动时间: 2004年01月14日 20:00:08 * 完成时间: 2003年01月14日 20:09:00 <1个晚上> * * 开发环境: Windows2000 Professional + SUN J2SE1.4.2 * 开发工具: Rational Rose2002 Enterprise + JCreator2.5Pro * * 文件名称: AixPoint.Java * 简 介: 正方形问题的低层处理类,抽象正方形问题的每个访问点信息 * * 备 注: <本系统的底层抽象> * * 修改时间1: *
******************************************************************************/
package CXXSoft.Aix;import Java.awt.Point;public class AixPoint extends Point{ private int moveUnit; public boolean aheadExcess; public boolean aboveExcess; //类构造器 public AixPoint()
{ aheadExcess = false; aboveExcess = false; moveUnit = 1;
} //类构造器 public AixPoint(int x,int y) { this(); this.x = x; this.y = y; } //类构造器 public AixPoint(Point p) { this(); this.x = p.x; this.y = p.y; } //向左移动(前进) public void goAhead() { this.x += moveUnit; } //向左的反方向移动(后退) public void goAheadReturn() { this.x -= moveUnit; } //向上移动 public void goAbove() { this.y += moveUnit; } //向上的反方向移动(后退) public void goAboveReturn() { this.y -= moveUnit; } //形成输出串 public String toString() { return "("+ x + "," + y +")"; }}
AixSquare源码：
/******************************************************************************* * <<AIX 程序设计大赛---AIX正方形问题>> * AIXContest ver1.0 * 开发作者: 成晓旭 * 项目简述: AIX程序设计的Java程序设计"AIX正方形问题"解决方案 * 启动时间: 2004年01月14日 20:28:00 * 完成时间: 2003年01月17日 00:16:00<4个晚上> * * 开发环境: Windows2000 Professional + SUN J2SE1.4.2 * 开发工具: Rational Rose2002 Enterprise + JCreator2.5Pro * * 文件名称: AixSquare.Java * 简 介: 正方形问题的核心处理类,抽象正方形算法处理过程 * * 备 注: <本系统的核心层抽象> * * 修改时间1: * * [问题描述]: * 任意给定一个正方形，将正方形的各边做n等分,并将相应各点连接成水平 * 或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线, * 自左向右或自下而上的方向,到达正方形的右上角(n,n), * 请用Java程序计算并输出所有可能的路径总数和具体线路. * 请提供相关Java源程序和n=2,3,4时的输出结果。输出结果按以下方式: * 以n=1为例: * n = 1 * Path1: (0,0) - (0,1) - (1,1) * Path2: (0,0) - (1,0) - (1,1) * Total = 2 * * [解答思路]: * 此问题的核心是一个"有向无环图"的遍历问题, * 解答的思想就是一个"试探"与"回溯"算法的抽象与实现.甚至比完整的 * "有向无环图"的遍历问题还要简单. * * [建模提示]: * 为了简化问题的处理过程,强调解决问题的实质性思路,在建模过程中, * 对遍历过程中每步"前进"的步长进行了"固定步长为1"的假设,即对将被 * n等分的正方形的边长,自动设置为n,以简化算法中对边的计算处理. * * [算法优化]: * 目前设计的算法有以下几处有待优化: * 1:此题是一般的"试探"与"回溯"算法一个特例,所以有些处理过程是可以省略的 * (目前实现的是一个标准的"试探"与"回溯"算法) * 2:由于题目自身的特殊性,对某些处理过程可做简化,以提高算法的执行效率 * (如:对进栈,出栈的处理,对访问队列的处理,对在正方形边上"前进"时的 * 回溯处理,对临界条件,到达目标点条件的判断等等) * 3:问题的本身及解答此题的思路是很具一般性的,但目前分析,设计的类结构过于特殊化. * ******************************************************************************/package CXXSoft.Aix;import Java.awt.Point;import Java.util.Stack;import Java.util.Vector;import Java.util.List;import CXXSoft.Aix.AixPoint;public class AixSquare{ //AIX正方形问题点遍历时前进方向常量定义 private final static int MOVE_AHEAD = 1; //向左 private final static int MOVE_ABOVE = 2; //向上 //AIX正方形问题点遍历时优先前进的方向常量定义 public final static int FIRST_MOVE_AHEAD = 101; //先从左至右,后从下向上 public final static int FIRST_MOVE_ABOVE = 102; //先从下向上,后从左至右 private int moveUnit; //当前算法处理的单位长度 private int nPart; //矩形边被等分的份数 private int firstMoveWay; //正方形问题线路优先前进方向 private int nAccess; //正确的通路总数 private Point startP; private Point endP; private String strPath; private Vector visitedPoint; //遍历过程中已经访问过的点队列(每找到一条通道后被清空,然后重新加载) private Stack visitStack; //遍历过程中的堆栈 private Vector rightAccess; //能到达目标点的正确通路队列 //算法访问的当前点 private AixPoint p; private void visitPoint() { if(strPath == null || strPath == "") strPath = "Path" + (nAccess + 1) +": " + p; else strPath += " - " + p; } //判断是否向左前进越界 private boolean isAheadExcess() { return (p.x > endP.x); } //判断是否向上前进越界 private boolean isAboveExcess() { return (p.y > endP.y); } //将当前轮的遍历结果点组成的遍历线路存储于rightAccess中 private void saveArriveLine() { String str = "",strAccess = ""; for(int i=0;i<visitedPoint.size();i++) { AixPoint q = (AixPoint)visitedPoint.get(i); str = (str == null || str == "") ? " Path" + (nAccess + 1) +": " : " - "; strAccess += str + q; } rightAccess.add(strAccess); } //判断是否前进到目标点 private boolean isArriveAim() { boolean isOK = false; isOK = ((p.x == endP.x) && (p.y == endP.y) &&(p.aheadExcess && p.aboveExcess)); if(isOK) { saveArriveLine(); nAccess++; strPath = ""; } return isOK; } //遍历的当前点进栈 private void pushPoint() { visitStack.push(p); } //遍历的当前点退栈 private void popPoint() { if(!visitStack.empty()) { p = (AixPoint)visitStack.pop(); } } //修改遍历堆栈中,参数指定的点的越界标志 private void setVisitStackExcess(AixPoint para,int flag) { for(int i=0;i<visitStack.size();i++) { AixPoint q = (AixPoint)visitStack.get(i); if(para == q) { switch(flag) { case MOVE_AHEAD: q.aheadExcess = true; break; case MOVE_ABOVE: q.aboveExcess = true; break; } } } } //遍历的当前点进入队列 private void enterList() { visitedPoint.add(p); } //遍历的当前点退出队列(将当前点在遍历队列中删除) private void exitList() { visitedPoint.remove(p); } //修改遍历的当前点队列中,参数指定的点的越界标志 private void setVisitedListExcess(AixPoint para,int flag) { for(int i=0;i<visitedPoint.size();i++) { AixPoint q = (AixPoint)visitedPoint.get(i); if(para == q) { switch(flag) { case MOVE_AHEAD: q.aheadExcess = true; break; case MOVE_ABOVE: q.aboveExcess = true; break; } } } } //判断当前点是否已经在曾经访问过的队列中 private boolean isVisited() { boolean isExist = false; for(int i=0;i<visitedPoint.size();i++) { if(p == (AixPoint)visitedPoint.get(i)) { isExist = true; break; } } return isExist; } //AIX正方形问题的"尝试前进"方法 private void attempt(int flag) { AixPoint q = new AixPoint(p); p = q; switch(flag) { case MOVE_AHEAD: //向左移动 p.goAhead(); //[向前尝试] break; case MOVE_ABOVE: //向上移动 p.goAbove(); //[向上尝试] } } //AIX正方形问题的"回溯后退"方法 private void backdate(int flag) { popPoint(); //[向后/向下回溯] pushPoint(); setVisitedListExcess(p,flag); setVisitStackExcess(p,flag); } //新版:goAlwaysLeft()方法 protected void goAlwaysLeftNew() { if(!isVisited()) { pushPoint();