论深度优先（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

Sample Output

/*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 = ;

struct{

    int r, c;

}sta, end, queue[Max * Max];

int len;

bool vis[Max][Max];

int dr[] = {-, -, -, -, , , , };

int dc[] = {-, , -, , -, , -, };

bool inmap(int r, int c){

    if(r >=  && r < len && c >=  && 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 << '' << endl;

            continue;

        }

        memset(vis, false, sizeof(vis));

        vis[sta.r][sta.c] = true;

        queue[].r = sta.r;

        queue[].c = sta.c;

        int head = , tail = , steps = ;

        bool find = false;

        while(!find){

            steps ++;

            int count = tail - head;

            while(!find && count --){

                for(int i = ; i < ; 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 ;

}

参考部分：

评价：

这份代码的优点很明显。相对与深度优先搜索来说，它只要每次访问一个层次，不会造成较大的空间浪费。

然后就是理解起来相对较为方便，只要搞清楚基本的思路和队列的用法，基本上磨磨蹭蹭的搞个几小时基本还是能够将结果返回出来的。

巴特西

论深度优先（DFS）和广度优先搜索（BF）的优点及不足（更新ing）

最新文章

热门文章