kinpoo
注册会员
初级会员
UID 30794
精华
0
积分 101
帖子 108
金钱 101 喜悦币
威望 0
人脉 0
阅读权限 20
注册 2004-8-30
状态 离线
|
[广告]: 代充Paypal帐号美元
递归实现连连看寻路算法~
学习C++不是很久 多多指教~
<?php
/**
* Author:郭剑波(KINPOO)
* Last Modify:2005/11/21 13:40
* Purpose:find path for lian lian kan
*/
/**
* api:bool FindPath(int x1,int y1,int x2,int y2);
* config function FindPath,getKey by note
* path array:path[][2] in function FindPath
*/
#include<iostream>
using namespace std;
const int MX=14,MY=12;
int arr[MX][MY]=
{
{0,0,0,0,0,0,0,1,1,1,0,1},
{5,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,11,12,100,0},
{1,0,4,4,0,0,9,0,0,0,0,0},
{0,0,2,0,3,0,0,0,0,0,0,0},
{3,0,0,0,0,8,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,7,0,0,0,1,1,0,0,0},
{0,1,0,1,0,1,0,6,0,0,0,0},
{0,1,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,0,1,0,0,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0,0,0}
};
void recordPath(int[][2],int,int);//for mazeOrder
void getKey(int,int,char,int[],int,int,int,int);//for mazeOrder
void mazeOrder(int,int,int,int,int[][2],int,int,bool*,char=0,int=0,int=-1,int=-1);//mazeOrder very important!!!
bool FindPath(int x1,int y1,int x2,int y2);//api
//测试用的~
void main(){
char p[5];
//cin>>p;
//for(int i=0;i<1000;i++)
FindPath(4,3,0,1);
cin>>p;
}
//测试用的~
bool FindPath(int x1,int y1,int x2,int y2)
{
int i;
const int MXX=MX,MYY=MY;//设置迷宫矩阵大小
int path[(MXX+MYY)*2][2];//用来存放路径的数组
//其实最坏的情况下存放路径的数组大小为
//(MXX>MYY ? MXX : MYY)*2 + (MXX<MYY ? MXX : MYY) - 2
bool is_con,iflock;//开始记录路径的开关
for(i=0;i<(MXX+MYY)*2;i++)
{//初始化数组为(-1,-1)... 必要
path[i][0]=path[i][1]=-1;//小于零即可
}
is_con=iflock=false;//初始化为false 非必要
mazeOrder(x1,y1,x2,y2,path,MXX,MYY,&iflock);//进行遍历迷宫并记录路径到path[][2]
if(path[0][0]>=0)
{//数组为不空
is_con=true;//设置返回值(连通)
}
//路径存放顺序:(x2,y2)->回溯->(x1,y1)
//用-1代表数组结束
//调试用的~
for(i=0;path[i][0]!=-1;i++)
cout<<path[i][0]<<"t"<<path[i][1]<<"n";
//调试用的~
return is_con;//返回是否连通
}
void recordPath(int path[][2],int x,int y)
{
static int key;
if(path[0][0]<0 || path[0][1]<0)
{//重新寻路时置零
key=0;
}
path[key][0]=x;
path[key][1]=y;
++key;
}
void getKey(int x,int y,char cway,int key[],int MXX,int MYY,int x2,int y2)
{
switch(cway)
{
case 'N': key[0]=x-1;key[1]=y; break;
case 'E': key[0]=x;key[1]=y+1; break;
case 'S': key[0]=x+1;key[1]=y; break;
case 'W': key[0]=x;key[1]=y-1; break;
default:break;
}
if(key[0]<0 || key[1]<0 || key[0]>=MXX || key[1]>=MYY
|| ((key[0]!=x2 || key[1]!=y2) && arr[key[0]][key[1]]!=0))
//全局变量迷宫矩阵 arr
//arr[key[0]][key[1]]!=0 0为无障碍物的标志
{//溢出 || (!=(x2,y2) && 障碍物)
key[0]=key[1]=-1;//小于零即可
}
}
void mazeOrder(int x1,int y1,int x2,int y2,int path[][2],int MXX,int MYY
,bool *iflock,char cway,int times,int x,int y)
{
if(times==3 || (x1==x2 && y1==y2)//转折次数超过两次 || 开始==目标
|| x1<0 || y1<0 || x1>=MXX || y1>=MYY //开始点溢出
|| x2<0 || y2<0 || x2>=MXX || y2>=MYY) //目标点溢出
{//可在此处直接加 arr[x1][y1]!=arr[x2][y2] 判断开始点与目标点是否想同
return;
}
if(x<0 || y<0 || x>=MXX || y>=MYY)
{//初始化入口参数
x=x1;y=y1;cway=0;times=0;
}
if(x==x2 && y==y2)
{//找到路径 加锁
*iflock=true;
}
char *ways;//方向优先级
if(x2>=x && y2>y) ways="ESWN";//+X轴加第四象限
else if(x2>x && y2<=y) ways="SWNE";//-Y轴加第三象限
else if(x2<=x && y2<y) ways="WNES";//-X轴加第二象限
else ways="NESW";//+Y轴加第一象限
for(int i=0,temp[2];ways[i]!=0 && !(*iflock);i++)
{
switch(cway)
{//不能直接回走
case 'N': if(ways[i]=='S') continue; break;
case 'E': if(ways[i]=='W') continue; break;
case 'S': if(ways[i]=='N') continue; break;
case 'W': if(ways[i]=='E') continue; break;
default : break;
}
getKey(x,y,ways[i],temp,MXX,MYY,x2,y2);//取得下一步的x,y
if(temp[0]>=0)
{//x,y有效时才继续往下走
mazeOrder(x1,y1,x2,y2,path,MXX,MYY,iflock,ways[i]
,times+((cway && ways[i]!=cway)?1:0)//转弯则加一
,temp[0],temp[1]);
}
}
if(*iflock)
{//回滚时记录路径
recordPath(path,x,y);
}
}
?>
| 
矛盾是发展的源泉。 |
|
