#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define NULL 0
const int nmax = 200
const int nend = 99 /*终点坐标的代表点*/
static char achar[10][10]
static int npayo = 0 /*0 表示空 1为非空*/
static int npayc = 0 /*0 表示空 1为非空*/
static int npay_x = 0/*起点*/
static int npay_y = 0
static int nend_x = 9/*终点*/
static int nend_y = 9
static int nnewpay_x
static int nnewpay_y
static int ndian = 101
static int nh
static long i = 10000000L
struct Spaydian
{
int ng
int nf /*路径评分*/
int nmy_x/*自己位置*/
int nmy_y
int nfatherx /*父节点*/
int nfathery
int nflag /* 0 wei O1 wei @ */
}
static struct Spaydian spaydian[200]
/* open close list 表 */
typedef struct spaylist
{
int n_f
int n_x
int n_y
int nfather_x
int nfather_y
struct spaylist *next
}
static struct spaylist *open_list, *close_list
static void smline()
static int sjudge(int nx,int ny,int i) /*判断在第nx列ny行向第i个方向走是否可以,可以返回1否则返回0。
i=1表示向右，2表示向下，3表示向左，4表示向上*/
static void spath()
static void spayshow(int nxx,int nyy)
static int sifopen( int nx,int ny) /*判断点是否在 open 表上*/
static int sifclose(int nx,int ny) /*判断点是否在 close 表上*/
static int snewx(int nx,int i)
static int snewy(int ny,int i)
static spaylist *creat() /*建立链表*/
static spaylist *del(spaylist *head,int num_x,int num_y) /*删除链表的结点*/
static spaylist *snewdianx(spaylist *head)/*新的点*/
static spaylist *snewdiany(spaylist *head)
static spaylist *insert(spaylist *head,int ndian) /* 点插入链表 */
static spaylist *srebirth(spaylist *head,int ndian) /*更新表*/
int main()
{
FILE *fp
char ach
int ni = 0 /*统计个数*/
int nii = 0 /*achar[nii][njj]*/
int njj = 0
if ((fp=fopen("route.txt","rt")) == NULL) /* 判断打开文件是否为空 */
{
printf("文件为空！~\n")
return 0
/* exit(1)*/
}
ach = fgetc(fp)
while(ach != EOF)
{
if(ach == 'O' || ach == '@')/*当值为@或O时候*/
{
spaydian[ni].ng = 0
spaydian[ni].nf = nmax
spaydian[ni].nmy_x = njj
spaydian[ni].nmy_y = nii
spaydian[ni].nfathery = -1
spaydian[ni].nfatherx = -1
if(ach == '@')
{
spaydian[ni].nflag = 1
}
else if(ach == 'O')
{
spaydian[ni].nflag = 0
}
ni++
achar[nii][njj] = ach
njj++
if(njj == 10)
{
nii++
njj = 0
}
} /*end if*/
ach = fgetc(fp)
}/*end while*/
smline() /* a*算法 */
fp=fopen("answer.txt","w")
for(int i=0i<10i++ )
{ for(int j=0j<10j++ )
{
printf("%c",achar[i][j])
if(j==9)
printf("\n")
fprintf(fp,"%c",achar[i][j])
if (j==9)
fprintf(fp,"\n")
}
}
fclose(fp)
return 0
}
/* a* 算法 */
static void smline()
{ close_list = open_list = NULL
open_list = creat()
while(open_list != NULL) /* 当open 表不为空时 */
{
open_list = del(open_list,npay_x,npay_y) /*删除open 链表的结点*/
if(npay_x == 9 &&npay_y == 9)
{
achar[9][9] = '='
spath() /*寻找并画出路径*/
break
}
for (int i=1i<=4i++) /*四个方向逐个行走，i=1向右 2向下 3向左 4向上*/
{
if (sjudge(npay_x,npay_y,i))
{
nnewpay_x = snewx(npay_x,i)
nnewpay_y = snewy(npay_y,i)
if(open_list != NULL)
npayo = sifopen(nnewpay_x,nnewpay_y)/*判断点是否在 open 表中*/
else
npayo = 0
if(close_list != NULL)
npayc = sifclose(nnewpay_x,nnewpay_y) /*判断点是否在 close 表中*/
else
npayc = 0
ndian = 10*nnewpay_x+nnewpay_y
if (npayo == 0 &&npayc == 0 ) /*点不在open表也不在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1 /*更新点的基本信息*/
nh = (nend - ndian)/10 + (nend - ndian)%10
spaydian[ndian].nf = spaydian[ndian].ng+nh
spaydian[ndian].nfathery = npay_y
spaydian[ndian].nfatherx = npay_x
spaydian[ndian].nmy_y = nnewpay_y
spaydian[ndian].nmy_x = nnewpay_x
open_list = insert(open_list,ndian)/*点插入open 表中*/
}
else if (npayo == 1) /*点在open表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1
nh = (nend - ndian)/10 + (nend - ndian)%10
if(spaydian[ndian].nf >(spaydian[ndian].ng+nh) &&spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh
open_list = srebirth(open_list,ndian)/*点插入open 表中*/
}
}
else if(npayc == 1) /*新生成的点在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1
nh = (nend - ndian)/10 + (nend - ndian)%10
if(spaydian[ndian].nf >(spaydian[ndian].ng+nh) &&spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh
close_list = srebirth(close_list,ndian)
close_list = del(close_list,nnewpay_x,nnewpay_y) /*删除close链表的结点*/
open_list = insert(open_list,ndian)/*点插入open 表中*/
}
}/*end else if*/
}/*end if*/
}/*end for*/
close_list = insert(close_list,(10*npay_x+npay_y))/*点插入close 表中*/
if(open_list != NULL)
{
npay_x = open_list->n_x
npay_y = open_list->n_y
}
}/*end while*/
if(open_list == NULL)
{printf("无路可走 \n")}
}
/*建立链表*/
spaylist *creat(void)
{
spaylist *head
spaylist *p1
int n=0
p1=(spaylist*)malloc(sizeof(spaylist))
p1->n_f = 18
p1->n_x = 0
p1->n_y = 0
p1->nfather_x = -1
p1->nfather_x = -1
p1->next = NULL
head = NULL
head=p1
return(head)
}
/*删除结点*/
spaylist *del(spaylist *head,int num_x,int num_y)
{
spaylist *p1, *p2
if(head == NULL)
{
printf("\nlist null!\n")
return (head)
}
p1 = head
while((num_y != p1->n_y ||num_x != p1->n_x )&&p1->next != NULL)
{
p2=p1
p1=p1->next
}
if(num_x == p1->n_x &&num_y == p1->n_y )
{
if(p1==head)
head=p1->next
else
p2->next=p1->next
}
return (head)
}
/*输出*/
static void spath()
{
int nxx
int nyy
nxx = spaydian[nend].nfatherx
nyy = spaydian[nend].nfathery
spayshow(nxx,nyy)
}
/*递归*/
void spayshow(int nxx,int nyy)
{ achar[nxx][nyy] = '='
if( nxx != 0 || nyy != 0 )
{
int nxxyy = 10*nxx+nyy
nxx = spaydian[nxxyy].nfatherx
nyy = spaydian[nxxyy].nfathery
spayshow(nxx,nyy)
}
}
/* 判断周围四个点是否可行 */
static int sjudge(int nx,int ny,int i)
{
if (i==1) /*判断向右可否行走*/
{
if (achar[nx][ny+1]=='O' &&ny<9)
{
return 1
}
else
return 0
}
else if (i==2) /*判断向下可否行走*/
{
if (achar[nx+1][ny]=='O' &&nx<9)
{
return 1
}
else
return 0
}
else if (i==3)/*判断向左可否行走 */
{
if (ny >0&&achar[nx][ny-1]=='O')
{
return 1
}
else
return 0
}
else if (i==4)/*判断向上可否行走 */
{
if (nx >0&&achar[nx-1][ny]=='O')
{
return 1
}
else
return 0
}
else
return 0
}
/* 求新的x点 */
static int snewx(int nx,int i)
{
if(i == 1)
nx = nx
else if(i == 2)
nx = nx+1
else if(i == 3)
nx = nx
else if(i == 4)
nx = nx-1
return nx
}
/* 求新的y点 */
static int snewy(int ny, int i)
{
if(i == 1)
ny = ny+1
else if(i == 2)
ny = ny
else if(i == 3)
ny = ny-1
else if(i == 4)
ny = ny
return ny
}
/*判定点是否在open表中*/
int sifopen(int nx,int ny)
{
spaylist *p1, *p2
p1 = open_list
while((ny != p1->n_y || nx != p1->n_x )&&p1->next != NULL)
{
p2 = p1
p1 = p1->next
}
if(nx == p1->n_x &&ny == p1->n_y)
return 1
else
return 0
}
/*判定点是否在close表中*/
int sifclose(int nx,int ny)
{
spaylist *p1, *p2
p1 = close_list
while((ny != p1->n_y ||nx != p1->n_x )&&p1->next != NULL)
{
p2=p1
p1=p1->next
}
if(nx == p1->n_x &&ny == p1->n_y)
return 1
else
return 0
}
/*插入结点*/
spaylist * insert(spaylist *head,int ndian)
{
spaylist *p0,*p1,*p2
p1=head
p0=(spaylist*)malloc(sizeof(spaylist))
p0->n_f = spaydian[ndian].nf
p0->n_x = spaydian[ndian].nmy_x
p0->n_y = spaydian[ndian].nmy_y
p0->nfather_x = spaydian[ndian].nfatherx
p0->nfather_x = spaydian[ndian].nfathery
p0->next = NULL
if(head==NULL)
{
head=p0
p0->next=NULL
}
else
{
while((p0->n_f >p1->n_f)&&(p1->next!=NULL))
{
p2=p1
p1=p1->next
}
if(p0->n_f <= p1->n_f)
{
if(head==p1)
head=p0
else
p2->next=p0
p0->next=p1
}
else
{
p1->next=p0
p0->next=NULL
}
}
return (head)
}
/* 更新链表 */
spaylist * srebirth(spaylist *head,int ndian)
{
spaylist *p1, *p2
p1=head
while(spaydian[ndian].nmy_x!=p1->n_x&&spaydian[ndian].nmy_x!=p1->n_x&&p1->next!=NULL)
{
p2=p1
p1=p1->next
}
if(spaydian[ndian].nmy_x==p1->n_x&&spaydian[ndian].nmy_x==p1->n_x)
{
p1->n_f = spaydian[ndian].nf
}
return (head)
}
1#include <iostream>2#include <queue>
3usingnamespace std
4
5struct knight{
6int x,y,step
7int g,h,f
8booloperator<(const knight &k) const{ //重载比较运算符
9return f >k.f
10}
11}k
12bool visited[8][8] //已访问标记(关闭列表)
13int x1,y1,x2,y2,ans //起点(x1,y1),终点(x2,y2),最少移动次数ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}}//8个移动方向
15priority_queue<knight>que //最小优先级队列(开启列表)
16
17boolin(const knight &a){ //判断knight是否在棋盘内
18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)
19returnfalse
20returntrue
21}
22int Heuristic(const knight &a){//manhattan估价函数
23return (abs(a.x-x2)+abs(a.y-y2))*10
24}
25void Astar(){ //A*算法
26knight t,s
27while(!que.empty()){
28t=que.top(),que.pop(),visited[t.x][t.y]=true
29if(t.x==x2 &&t.y==y2){
30ans=t.step
31break
32}
33for(int i=0i<8i++){
34s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1]
35if(in(s) &&!visited[s.x][s.y]){
36s.g = t.g +23//23表示根号5乘以10再取其ceil
37s.h = Heuristic(s)
38s.f = s.g + s.h
39s.step = t.step +1
40que.push(s)
41}
42}
43}
44}
45int main(){
46char line[5]
47while(gets(line)){
48x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1'
49memset(visited,false,sizeof(visited))
50k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h
51while(!que.empty()) que.pop()
52que.push(k)
53Astar()
54printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans)
55}
56return0
57}
58
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）