maze.cpp

迷宫源程序,程序自动搜索路径

// 迷宫.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream.h>

const m=6,n=8;

int maze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,1,0,1,0,1,1},
	{1,1,0,0,1,1,0,0,0,1},
	{1,0,0,0,0,0,0,1,1,1},
	{1,1,1,0,1,1,0,0,0,1},	
	{1,0,0,0,0,0,1,0,1,1},	
	{1,1,0,1,0,0,0,0,0,1},	
	{1,1,1,1,1,1,1,1,1,1}};
int mark[m+2][n+2];
int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };

bool SeekPath(int x,int y)
//从迷宫中坐标点(x,y)的位置寻找通向终点(m,n)的路径,若找
//到则返回true,否则返回false,(x,y)的初始值通常为(1,1)
{
  int i; //循环变量,代表从当前位置移到下一个位置的方向

  int g,h; //作为下一个位置的行坐标和列坐标

  if( (x==m) &&(y==n) ) return true; //到达出口点返回true结束递归

  for(i=0; i<4; i++)

  {

      g=x+move[i][0];   //求出下一个位置的行坐标和列坐标
      h=y+move[i][1];

     if( (maze[g][h]==0) &&(mark[g][h]==0) )
	 {
     mark[g][h]=1; //置mark数组中对应位置为1,表明已访问过

      //当条件成立(即返回true)时,表明从(g,h)到终点存在通路,应输出该位置坐标,
      //同时返回true结束递归,否则进入下一轮循环,向下一个方向试探
      if(SeekPath(g,h) )    
      {
      cout<<"("<<g<<","<<h<<"),";
      return true;
	  }
	 
	}
  }
  
   //当入口点的所有方向都访问完后,表明没有通向终点的路径,应打印出没有路径信息

   if( (x==1) && (y==1) ) cout<<"No path!"<<endl;
   
   //从当前位置(x,y)没有通向终点的路径,应返回false

   return false; 
}

int main(int argc, char* argv[])
{

	int i,j;
     //cout<<"请输入迷宫数据(按行输入):"<<endl;
//	for(i=0; i<m+2; i++)
	//	for(j=0; j<n+2;j++)
		//	cin>>maze[i][j];
	
	

	for(i=0; i<m+2; i++)
		for(j=0; j<n+2; j++)
			mark[i][j]=0;

	mark[1][1]=1;

	if(SeekPath(1,1) )
		cout<<"("<<1<<","<<1<<")"<<endl;
	return 0;
}