POJ3278 ＆＆ POJ3984 （BFS 解题模板）

为了下个星期的蓝桥杯国赛，这周要抓紧刷搜索题。。。。

先来说说BFS，广度优先搜索，一般都会利用到Queue，BFS里正常是没有递归的，开始时要设置一个visited[maxn]数组来标记已经访问过的节点，扩展节点时一定要注意判别是否已经访问过以及判别子节点是否有效（是否已经出界了）。BFS常用于解决最短路径等问题。

解题模板如下：

1. 把初始节点S0放入Queue中；
2. 如果Queue为空，则问题无解，失败退出；
3. 把Queue里的第一个节点取出，标记为已访问，并记该节点为n；
4. 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
5. 若节点n不可扩展，则转第2步；
6. 扩展节点n，将其还未被访问过的子节点（判重）放入Queue的尾部，并将这些子节点标记为已访问。转2；

流程图：截图来自北大郭炜老师的网课ppt mooc北大算法网课

深搜和广搜的比较    来自郭炜老师ppt

• 广搜一般用于状态表示比较简单、求最优策略的问题

           优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最                         短的解。                                      

           缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保                          存所有扩展出的状态，占用的空间大。

• 深度搜索几乎可以用于任何问题

            只需要保存从起始状态到当前状态路径上的节点

一般BFS有两种问题：

• 一个是求最短路径的步数（或者是时间）问题，这种问题关键是要记录下每层搜索的层数，可以用一个数组a，a[i] = a[i-1]+1，在新节点进入队列之前，将新节点 i 的层数更新为他的父节点的层数+1。
• 另一个是要输出最短路径的路线，这种情况下，可以创建一个简单的结构体，里面加入parent成员，在新节点 i 进入队列前，将父节点的位置记录下来，找到目标节点后，就可以顺着parent域找到初始节点，然后输出整个路线。

下面是两道自己初学写出来的BFS。

POJ 3278 抓住那头牛

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

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

AC代码：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 100000;
int steps[maxn+5];        //steps[i]表示走到位置i做需要的步数
int visited[maxn+5];      //是否访问过标记
int N, K;
int time = 0;             //层数/步数/时间

void bfs(int n);

int main(void)
{
    memset(steps, 0, sizeof(steps));
    memset(visited, 0, sizeof(visited));
    
    cin >> N >> K;
    steps[N] = 0;
    visited[N] = 1;
    bfs(N);

    cout << time << endl;

    return 0;
}

void bfs(int n)
{
    queue<int> q;
    q.push(n);                  //初始节点入队

    while(!q.empty())           //只要队列不为空，就一层一层地搜索下去
    {
        int cur = q.front();    //取出队首
        q.pop(); 

        if(cur == K)            //到达目标节点，记录下总步数后，结束
        {
            time = steps[K];
            return;
        }
        else                    //还未到目标节点，扩展节点
        {
            if(cur-1 >= 0 && !visited[cur-1]){        //判重以及判断子节点是否越界
                visited[cur-1] = 1;                   //入队前标记已访问过
                q.push(cur-1);                        //子节点入队
                steps[cur-1] = steps[cur] + 1;        //记录子节点层数为父节点层数+1
            }
            if(cur + 1 <= maxn && !visited[cur+1]){
                visited[cur+1] = 1;
                q.push(cur+1);
                steps[cur+1] = steps[cur] + 1;
            }    
            if(cur*2 <= maxn && !visited[cur*2]){
                visited[cur*2] = 1;
                q.push(2*cur);
                steps[cur*2] = steps[cur] + 1;
            }   
        }     
    }
}

POJ 3984 迷宫问题

Description

定义一个二维数组： 

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

此题因为要记录下路径，如果用队列的话，出队后再找父节点比较麻烦，可以用vector来做，push_back模拟入队，index下标递增模拟出队。

AC代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

struct node{
    int x;
    int y;
    node(int i, int j, int k = 0) : x(i), y(j), p(k) {}
    int p;          //记录该节点的父节点在vector中的下标
};

int maze[5][5];
int visited[5][5];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<node> v;    //记录整个搜索过程，通过node的p成员构成一条路径
vector<node> ans;  //存放最终结果路径

bool judge(node n);
void bfs();
void print();

int main(void)
{
    memset(visited, 0, sizeof(visited));

    // ifstream fin("in.txt");
    // cin.rdbuf(fin.rdbuf());
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
        {
            cin >> maze[i][j];
        }
    }
    
    bfs();
    print();

    return 0;
}

void bfs()
{
    v.push_back(node(0, 0));        //初始节点模拟入队
    visited[0][0] = 1;
    int index = 0;                  //模拟队首的下标

    while(!v.empty())
    {
        node cur = v[index];
        if(cur.x == 4 && cur.y == 4)      //走到目标节点
        {
            ans.push_back(cur);           //将目标节点的父节点单独存起来，方便输出路径
            return;
        }
        else
        {
            for(int i = 0; i < 4; ++i)    //扩展节点，对于节点n，可扩展的子节点就是四个方向上的相邻节点
            {
                node now(cur.x+dx[i], cur.y+dy[i]);
                if(judge(now)){           //注意判重和是否越界
                    now.p = index;        //记录下入队节点的父节点
                    v.push_back(now);
                    visited[now.x][now.y] = 1;
                }
            }
        }
        index++;      //index递增，模拟队首
    }
}

bool judge(node n)   //对节点判重以及判别是否有效
{
    if(n.x >= 0 && n.x < 5 && n.y >= 0 && n.y < 5 && !visited[n.x][n.y] && maze[n.x][n.y] == 0)
        return true;
    return false;
}

void print()
{
    int i = 0;
    while(ans[i].p != 0){             //父节点域不为空，就加入ans，构成一整条所要求的路径
        ans.push_back(v[ans[i].p]);
        i++;
    }
    ans.push_back(v[0]);              //记得加入初始节点
    reverse(ans.begin(), ans.end());  //倒转，使路径正序输出
    for(int i = 0; i < ans.size(); ++i)
        cout << "(" << ans[i].x << ", " << ans[i].y << ")" << endl;
}