骑士问题--特殊的bfs
http://dl.iteye.com/upload/attachment/483033/7e1b7851-cfe4-3cf7-b6ea-00e9edf4eee7.png这个是来自 国际大学生程序设计竞赛例题解（1）的题目
很简单的一道搜索题目，但是没有使用dfs，
使用的是特殊的bfs，非常巧妙
代码
/*Qi Shi Wen Ti similar to eight queens use bfs() to get the min step */#include <stdio.h>#include <string.h>#include <stdlib.h>int queue;int matrix;int startX,startY,endX,endY;int head = -1,tail = 0;int dir = {{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};void put(int x,int y){tail ++;if(tail >= 1000)tail = tail % 1000;queue = x;queue = y;}void get(int * x,int * y){head ++;if(tail < head){printf("queue error!\n");exit(0);}*x = queue;*y = queue;}int queueEmpty(){return tail < head ? 1:0; }/* the problem is how to calculate the stepit seems like it's hard to find out one step's next step in the bfs searchwhile it is easy in the dfs search; standard bfs*/void bfs(int startX,int startY,int endX,int endY){int curX,curY;int minStep=0,step=0;;put(startX,startY);while(! queueEmpty()){get(&curX,&curY);matrix = 1;if(curX == endX && curY == endY){if(step > minStep)minStep = step;}else if( 1) {}else{for(int j=0;j<8;j++){curX += dir;curY += dir;if(matrix != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8)put(curX,curY);}}}}/*special Bfs it visited all nodes in a layer (just a layer's node int bfs tree) in a round*/int specialBfs(int startX,int startY,int endX,int endY){int head =0,tail =1,tmpTail;int step = 0;int curX = startX,curY = startY;queue = startX;queue = startY;matrix = 1;while(head <tail){step ++;tmpTail = tail;for(int i=head;i<tail;i++) //一次访问 整个树的一层节点，非常巧妙{for(int j=0;j<8;j++){curX = queue + dir;curY = queue + dir;if(matrix != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8){queue = curX;queue = curY;tmpTail ++; // here we must add tmpTail after put nodein queuematrix = 1;if(curX == endX && curY == endY)return step;}}}head = tail;tail = tmpTail; }return -1;}int main(){freopen("in.txt","r",stdin);int barrierCount;char c1,c2;scanf("%d\n",&barrierCount);for(int i=0;i<barrierCount;i++){scanf("%c%c ",&c1,&c2);matrix = 1;}scanf("%c%c\n",&c1,&c2);startX = c1 - 'a';startY = c2 - '1';scanf("%c%c\n",&c1,&c2);endX = c1 - 'a';endY = c2 - '1';printf("%d\n",specialBfs(startX,startY,endX,endY));fclose(stdin);return 0;}
页:
[1]