本文主要是介绍Knight Moves -uva 简单的BFS遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 10 + 5
#define LEN 100 + 10
using namespace std;
int dist[MAX_SIZE][MAX_SIZE];/*记录坐标点到起始点的距离*/
void bfs(int x,int y)
{int u=x*8+y,v;/*对一个一个的格子进行编号*/int queue[LEN];int dx[8]={-1,-2,-2,-1,1,2,2,1};/*控制方向*/int dy[8]={2,1,-1,-2,-2,-1,1,2};int visa[LEN][LEN]={0};/*记录节点是否被访问过*/int front=0,back=0,d,nx,ny;visa[x][y]=1;queue[back++]=u;/*开始遍历*/while(front<back){u=queue[front++];x=u/8;y=u%8;for(d=0;d<8;d++){nx=x+dx[d];ny=y+dy[d];/*这是新的坐标*/if(nx>=0&&ny>=0&&nx<8&&ny<8&&!visa[nx][ny]){visa[nx][ny]=1;dist[nx][ny]=dist[x][y]+1;v=8*nx+ny;queue[back++]=v;}}}
}
int main()
{char p,q;int m,n,i,j,k,x1,x2,y1,y2;while(scanf("%c%d %c%d",&p,&y1,&q,&y2)!=EOF){getchar();x1=p-'a';x2=q-'a';y1--;y2--;/*建立一下新的坐标系*//*printf("(%d,%d),(%d,%d)\n",x1,y1,x2,y2);*/bfs(x1,y1);/*传入开始遍历的坐标*//*for(i=0;i<8;i++){for(j=0;j<8;j++)printf("%d ",dist[i][j]);printf("\n");}*/printf("To get from %c%d to %c%d takes %d knight moves.\n",p,y1+1,q,y2+1,dist[x2][y2]);memset(dist,0,sizeof(dist));}return 0;
}
这篇关于Knight Moves -uva 简单的BFS遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!