骑士问题--特殊的bfs

?这个是来自 国际大学生程序设计竞赛例题解（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[1000][2];int matrix[8][8];int startX,startY,endX,endY;int head = -1,tail = 0;int dir[8][2] = {{-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[tail][0] = x;queue[tail][1] = y;}void get(int * x,int * y){head ++;if(tail < head){printf("queue error!\n");exit(0);}*x = queue[head][0];*y = queue[head][1];}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[curX][curY] = 1;if(curX == endX && curY == endY){if(step > minStep)minStep = step;}else if( 1) {}else{for(int j=0;j<8;j++){curX += dir[j][0];curY += dir[j][1];if(matrix[curX][curY] != 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[head][0] = startX;queue[head][1] = startY;matrix[curX][curY] = 1;while(head <tail){step ++;tmpTail = tail;for(int i=head;i<tail;i++) //一次访问 整个树的一层节点，非常巧妙{for(int j=0;j<8;j++){curX = queue[i][0] + dir[j][0];curY = queue[i][1] + dir[j][1];if(matrix[curX][curY] != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8){queue[tmpTail][0] = curX;queue[tmpTail][1] = curY;tmpTail ++; // here we must add tmpTail after put node  in queuematrix[curX][curY] = 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[c1-'a'][c2-'1'] = 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;}

?

?