迷宫问题

再过两个月就要软考了，在准备的过程中，我发现算法是我的软肋，尤其是递归和回溯，一直不是很明白。最近在书上看了个题目，是迷宫问题。虽然我知道这种问题要采用回溯，反复试探，但具体到代码实现，就力不从心。于是认真阅读了C代码，自认为有点头绪了，就改成java重新实现一下。虽然大致结构没变，但通过自己写，感觉提高了不少。以下是代码：

public class Maze {

	/*迷宫行数*/
	public static final int M = 12;
	/*迷宫列数*/
	public static final int N = 15;
	/*迷宫图，0代表通，1代表不通*/
	/*最终解的路径上的元素置为8，曾经到达过，但无路可走而被迫回溯的元素置为4*/
	public static int p[][]=
	{
		{0,1,0,0,0,1,1,0,0,0,1,1,1,1,1},
		{1,0,0,0,1,1,0,1,1,1,0,0,1,1,1},
		{0,1,1,0,0,0,0,1,1,1,1,0,0,1,1},
		{1,1,0,1,1,1,1,0,1,1,0,1,1,0,0},
		{1,1,0,1,1,1,1,0,1,1,0,1,1,0,0},
		{1,1,0,1,0,0,1,0,1,1,1,1,1,1,1},
		{0,0,1,1,0,1,1,1,0,1,0,0,1,1,1},
		{0,1,1,1,1,0,0,1,1,1,1,1,1,1,1},
		{0,0,1,1,0,1,1,0,1,1,1,1,1,0,1},
		{1,1,0,0,0,1,1,0,1,1,0,0,0,0,0},
		{0,0,1,1,1,1,1,0,0,0,1,1,1,1,0},
		{0,1,0,0,1,1,1,1,1,0,1,1,1,1,0}
	};
	public static void maze(int p[][],int m,int n)
	{
		/*行前进方向：右、右下，下、左下、左、左上、上、右上*/
		int is[] = {0,1,1,1,0,-1,-1,-1};
		/*列前进方向：右、右下，下、左下、左、左上、上、右上*/
		int js[] = {1,1,0,-1,-1,-1,0,1};
		int stack[] = new int[3*M*N];
		int top;
		int i,j,v,g,h,jt = 0;
		top = 0;
		i =j = v = 0;
		if(p[0][0]!=0)/*入口无路可走，提示无路，返回*/
		{
			p[0][0] = 4;
			System.out.println("No Path!");
			return;
		}
		while(top!=0||v!=7)/*只要没有退回到起点或者其余7个方向还有方向没走*/
		{
			/*选择一个方向*/
			g = i+is[v];
			h = j+js[v];
			jt = 0;
			if(g>-1&&g<m&&h>-1&&h<n)
			{
				/*已经到达了中点*/
				if(g==m-1&&h ==n-1&&p[m-1][n-1]==0)
				{
					p[i][j] = 8;
					p[g][h] = 8;
					return;    /*找到路径,返回*/
				}
				/*有通路*/
				if(p[g][h]==0)
				{
					p[g][h] = 4;
					p[i][j] = 8;  /*前一步位置上置为8*/
					/*入栈，记录下前一步*/
					stack[top]=i;
					stack[top+1]=j;
					stack[top+2]=v;
					top += 3;
					i = g;
					j = h;
					v = 0;
					jt = 1;	/*标记为新发现的节点*/
				}
			}
			if(jt == 0)
			{
				/*换个方向试试*/
				if(v<7)
				{
					v++;
				}
				/*所有方向都试完了，开始回溯*/
				else
				{
					/*如果上个结点也走投无路的，循环往上回退*/
					while(top!=0 && stack[top-1]==7)
					{
						p[stack[top-3]][stack[top-2]]=4;/*无路，栈中元素置为4，并退栈*/
						top-=3;
					}
					/*继续搜索上一个节点的其它方向*/
					if(top!=0)
					{
						i = stack[top-3];
						j = stack[top-2];
						v = stack[top-1];
						p[i][j] = 4;
						top-=3;
					}
				}
			}
		}
		System.out.println("No Path!");
		return;
	}
	
	public static void main(String[] args) {
		int i,j;	
		maze(p,12,15);
		for(i = 0;i<M;i++)
		{
			for(j = 0;j<N;j++)
			{
				System.out.print(p[i][j]);
			}
			System.out.println();
		}

	}

}

 

评论

1 楼 wonderlandsh 2009-06-15  

有C代码实现的吗？