首页 > 代码库 > 论深度优先（DFS）和广度优先搜索（BF）的优点及不足（更新ing）
论深度优先（DFS）和广度优先搜索（BF）的优点及不足（更新ing）
例题：
POJ 1915 Knight Moves 骑士遍历问题(跳马问题)
在一个m*m的棋盘上，从任意一个给定的位置(sx , sy)出发，为象棋中的马找一条路通过最少的步数到达另一位置(ex ,ey)，输出最少所需要的步数。
利用bfs求解。
当马在位置(x , y)的时候其后继节点(后继选择)是什么？
对于马，有八个方向可以选择，马可以跳到如下几个位置：
(x+2 , y+1) ,
(x+1 , y+2 ) ,
(x-1 , y+2) ,
(x-2 , y+1)，
(x+2 , y -1) ,
(x+1 , y-2 ) ,
(x-1 , y-2) ,
(x-2 , y-1)；
那么后继状态也就是这些可选的位置了。
当然要判断这些后继位置是否会越界，去掉那些会越界的节点。
Sample Input
380 07 01000 030 50101 11 1
Sample Output
5280
/*Knight Moves*/
#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
int x ;
int y ;
int d ;
void init(int nx , int ny , int nd)
{
x = nx ;
y = ny ;
d = nd ;
}
};
bool visit[MAXN][MAXN];
int bfs(Node source , Node target){
queue<Node> Q ;
source.d = 0 ;
Q.push(source);
memset(visit , 0 , sizeof(visit)) ;
visit[source.x][source.y] = 1 ;
while(!Q.empty()){
Node a = Q.front() ;
Q.pop() ;
int x = a.x ;
int y = a.y ;
for(int i = 0 ; i < 8 ; i ++){
int nx = x + dir[i][0] ;
int ny = y + dir[i][1] ;
//判断新的节点是否会越界
if(nx < 0 || nx >= m || ny >= m || ny < 0)
continue ;
if(visit[nx][ny])
continue ;
//判断后继节点是否是目标节点
if(target.x == nx && target.y == ny)
return a.d + 1 ;
visit[nx][ny] = 1 ;
Node c ;
c.init(nx , ny , a.d + 1) ;
Q.push(c) ;
}
}
return -1 ;
}
//////////////////////////////////////////////////////////////////////////////////////////////
AC代码：
#include<iostream>using namespace std;const int Max = 305; struct{ int r, c;}sta, end, queue[Max * Max];int len;bool vis[Max][Max];int dr[8] = {-2, -2, -1, -1, 1, 1, 2, 2};int dc[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; bool inmap(int r, int c){ if(r >= 0 && r < len && c >= 0 && c < len) return true; return false;} int main(){ int n; cin >> n; while(n --){ cin >> len; cin >> sta.r >> sta.c >> end.r >> end.c; if(sta.r == end.r && sta.c == end.c){ // 记得加起点等于终点的判断。 cout << ‘0‘ << endl; continue; } memset(vis, false, sizeof(vis)); vis[sta.r][sta.c] = true; queue[0].r = sta.r; queue[0].c = sta.c; int head = 0, tail = 1, steps = 0; bool find = false; while(!find){ steps ++; int count = tail - head; while(!find && count --){ for(int i = 0; i < 8; i ++){ int r = queue[head].r + dr[i]; int c = queue[head].c + dc[i]; if(r == end.r && c == end.c){ find = true; break; } if(inmap(r, c) && !vis[r][c]){ vis[r][c] = true; queue[tail].r = r; queue[tail].c = c; tail ++; } } head ++; // 一开始把head++写到外面，卡了很久，以后要小心。 } } cout << steps << endl; } return 0;}