c语言技巧之搜索剪枝

To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.

大概题意：

一个8行8列的棋谱，任意给出knight的两个位子，问按照knight的走法，从其中的一个位子出发，问至少需要经过几步到达另外一个位子。 行用1-8表示，列用a-h表示。 输出格式见上。

解题思想：

起始位子作为初始结点进入队列，然后取出第一个结点，把knight能走的位子依次全

部进入队列，在进入队列前判断是否为终结点。开辟一个二维数组记录步数。

参考代码：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

#include #include

using namespace std; struct point { int x,y; };

int chessboard[8][8];//记录步数

vector v; point p; bool find; int index;

int start_x,start_y,end_x,end_y; void deal(int x,int y,int time) { if(x==end_x&&y==end_y) { find=true; return; } if(x-2>=0&&y-1>=0&&chessboard[x-2][y-1]==-1) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

chessboard[x-2][y-1]=time+1; p.x=x-2; p.y=y-1; v.push_back(p); }

if(x-2>=0&&y+1<8&&chessboard[x-2][y+1]==-1) { chessboard[x-2][y+1]=time+1; p.x=x-2; p.y=y+1; v.push_back(p); }

if(x+2<8&&y+1<8&&chessboard[x+2][y+1]==-1) { chessboard[x+2][y+1]=time+1; p.x=x+2; p.y=y+1; v.push_back(p); }

if(x+2<8&&y-1>=0&&chessboard[x+2][y-1]==-1) { chessboard[x+2][y-1]=time+1; p.x=x+2; p.y=y-1; v.push_back(p); }

if(x-1>=0&&y+2<8&&chessboard[x-1][y+2]==-1) { chessboard[x-1][y+2]=time+1; p.x=x-1; p.y=y+2; v.push_back(p); }

if(x-1>=0&&y-2>=0&&chessboard[x-1][y-2]==-1) { chessboard[x-1][y-2]=time+1; p.x=x-1; p.y=y-2; v.push_back(p); }

if(x+1<8&&y+2<8&&chessboard[x+1][y+2]==-1) { chessboard[x+1][y+2]=time+1; p.x=x+1;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ?

? ?

p.y=y+2; v.push_back(p); } if(x+1<8&&y-2>=0&&chessboard[x+1][y-2]==-1) { chessboard[x+1][y-2]=time+1; p.x=x+1; p.y=y-2; v.push_back(p); } }

int main() { char _s,_e; int s,e; while (cin>>_s>>s>>_e>>e) { start_x=(int)(_s-'a'); start_y=s-1; end_x=(int)(_e-'a'); end_y=e-1;

memset(chessboard,-1,sizeof(chessboard)); chessboard[start_x][start_y]=0; p.x=start_x; p.y=start_y; v.clear(); v.push_back(p); find=false; index=0; while (!find) {

deal(v[index].x,v[index].y,chessboard[v[index].x][v[index].y]); index++; } cout<<\\knight moves.\ } return 0;

?

}

（2） 宽搜经典

3278 Catch That Cow

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute

* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint