啊哈算法（4）—万能的搜索

深度优先搜索DFS
深度优先搜索的关键在于解决“当下该如何做”。至于下一步怎么做与当下该如何做是一样的。深度优先搜索的基本模型：

void dfs(int step)
{
    判断边界
    尝试每一种可能for(i=1;i<=n;++i)
    继续下一步dfs(step+1);
}

例1：求1到n的全排列，n为1~9之间任意一个数。

//求1到n的全排列  想相有n个盒子往里面放牌
#include<iostream>

using namespace std;

int a[10], book[10], n; 

void dfs(int step)  //站在第step个盒子前面
{
    if (step == n+1) //边界条件  到n+1时说明前面都已经放好
    {
        for (int i = 1; i <= n; ++i)
        {
            cout << a[i] << " " ;
        }
        cout << endl;
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            if (book[i] == 0)  //对每一种还没有尝试的进行尝试 为0的时候表示第i种还没有进行尝试
            {
                book[i] = 1;    
                a[step] = i;
                dfs(step + 1);
                book[i] = 0;   //尝试完之后要收回
            }
        }
    }
}

int main()
{
    cin >> n;//n位于1到9之间
    dfs(1);//现在站在第1个前面
    getchar();
}

例2：有1到9几个号码牌，将其填入括号中，使得（）（）（）+（）（）（）=（）（）（）。
其实就是对其求个全排列，并且判断一下a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]=a[7]*100+a[8]*10+a[9]是否满足，不在列举出代码。

例3：解救小哈，输入几行数，第一行两个数n，m。接下来的n行m列为迷宫，其中0表示可以走的地方，1表示障碍物。最后一行4个数，前两个表示迷宫的入口的x和y的坐标。后两个为小哈的位置。求出最短的步数。

#include<iostream>
#define INT_MAX 0x7fffffff;
using namespace std;

int a[51][51], book[51][51], min = INT_MAX;

int n, m, p, q;
void dfs(int x, int y, int step)
{
    int next[4][2] = { { 0,1 },//向右走 
                        { 1,0 },//向下走
                        { 0,-1 },//向左走 
                        { -1,0 } };//向上走
    if (x == p&&y == q)
    {
        if (step < min)
            min = step;
    }
    else
    {
        for (int k = 0; k <= 3; ++k)   //枚举四种走法
        {
            int tx = x + next[k][0];
            int ty = y + next[k][1];
            if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
                continue;

            if (a[tx][ty] == 0 && book[tx][ty] == 0) //判断是否为障碍物或者已经走过  
            {
                book[tx][ty] = 1;
                dfs(tx, ty, step + 1);
                book[tx][ty] = 0;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    int startx, starty;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    cin >> startx >> starty;

    //从起点开始搜索 标记为已经走过
    book[startx][starty] = 1;
    dfs(startx, starty, 0);
    cout << min << endl;

}

广度优先搜索BFS
BFS是一种层层递进的搜索方式，通常通过队列来完成，队列中存放的节点层次不超过一。
例1：与上面一个例子相同，不过这里将会采用广度优先搜索的方法完成，这里使用一个数组来模拟一个队列。

#include<iostream>
#define INT_MAX 0x7fffffff;
using namespace std;

struct note
{
    int x;   //横坐标
    int y;   //纵坐标
    int f;   //父亲在队列中的编号，用于输出路径
    int s;   //步数
};

int main()
{
    int a[51][51], book[51][51];
    struct note que[2501];// 地图大小为50*50，因此队列中的元素不会超过2500个
    int n, m, p, q;
    cin >> n >> m;
    int startx, starty;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    cin >> startx >> starty>>p>>q;

    int next[4][2] = { { 0,1 },//向右走 
                        { 1,0 },//向下走
                        { 0,-1 },//向左走 
                        { -1,0 } };//向上走
    //队列初始化        
    int head = 1,tail=1;    //队列的头和尾后指针
    que[head].x = startx;
    que[head].y = starty;
    que[head].f = 0;
    que[head].s = 0;
    tail++;
    //从起点开始搜索 标记为已经走过
    book[startx][starty] = 1;

    int flag = 0;//标记是否到达目标地。
    while (head < tail)   //head和tail范围内表示队列的元素，即队列不为空的时候
    {
        for (int k = 0; k <= 3; ++k)   //枚举四种走法
        {
            int tx = que[head].x + next[k][0];
            int ty = que[head].y + next[k][1];
            if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
                continue;

            if (a[tx][ty] == 0 && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;   //不用还原，不同于DFS每个点进入一次队列

                //将新的点插入队列中  
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].f = head;//这个节点是head扩展出来的
                que[tail].s = que[head].s + 1;//这里的步数类似于层数，队列中元素层数不超过1
                tail++;
            }
            if (tx == p&&ty == q)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            break;
        head++;//相当于出队操作
    }
    cout << que[tail - 1].s << endl;//此时即为最小步长 可以通过note.f来打印出路径

}

DFS BFS实例
例1：解救炸弹人，输入一个n 行 m列的地图其中#表示城墙，G表示敌人，.表示空地，试问在何处安放炸弹可以炸死最多的敌人，一个炸弹可以炸死一行一列的敌人（遇到城墙不可以越过）。
如下输入实例：

13 13 3 3 //地图大小以及起始位置
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############

解法1：采用BFS判断，可以到达的空地，并且统计每个空地上安放炸弹时可以炸死的敌人数目，代码如下：

#include<iostream>

using namespace std;

struct note
{
    int x;
    int y;
};

char a[20][20];  //用来存储地图

int getnum(int x, int y) //统计可以炸毁多少个敌人
{
    int i, j, sum = 0;
    //向右统计
    i = x, j = y;
    while (a[i][j]!='#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        j++;
    }
    //向左统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        j--;
    }
    //向下统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        i++;
    }
    //向上统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        i--;
    }
    return sum;
}
int main()
{
    struct note que[401];// 假设地图大小不超过20*20，扩展队列不会超过401
    int head, tail;//队列的头和尾
    int book[20][20] = {0};//用来标记当前点是否走过
    int next[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//可以走的四个方向
    int sum, max = 0, mx, my;//记录最大可以炸死的敌人个数，和放置炸弹的坐标
    int n, m, startx, starty; //地图的大小行数和列数 以及起使位置
    cin >> n >> m >> startx >> starty;

    for (int i = 0; i <= n - 1; ++i)   //存入地图
        for (int j = 0; j <= m - 1; ++j)
            cin >> a[i][j];

    //起点入队
    head = 1, tail = 1;
    que[head].x = startx;
    que[head].y = starty;
    tail++;
    book[startx][starty] = 1;
    max = getnum(startx, starty);
    mx = startx, my = starty;
    //遍历整个图
    while (head<tail)
    {
        int tx, ty;
        for (int k = 0; k < 4; ++k) //枚举四个方向
        {
            tx=que[head].x + next[k][0];
            ty=que[head].y + next[k][1];
            if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1)  //不合法 旧尝试下一种情况
                continue;

            if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
            {
                book[tx][ty] = 1;
                que[tail].x = tx;   //入队
                que[tail].y = ty;
                tail++;

                sum = getnum(tx, ty);//统计当前点放置炸弹可以炸死多少敌人
                if (sum > max)    //更新当前最大值以及放置炸弹的位置
                {
                    max = sum;
                    mx = tx;
                    my = ty;
                }
            }
        }
        head++;//  出队
    }
    cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
    system("pause");
}

解法2：采用DFS判断每一个点，过程如****意这里遍历到每个点就可以，所以不用回溯）

#include<iostream>

using namespace std;

char a[20][20];  //用来存储地图
int book[20][20];//用来标记当前点是否走过
int sum, max, mx, my;//记录最大可以炸死的敌人个数，和放置炸弹的坐标
int n, m, startx, starty; //地图的大小行数和列数 以及起使位置

int getnum(int x, int y) //统计可以炸毁多少个敌人
{
    int i, j, sum = 0;
    //向右统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        j++;
    }
    //向左统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        j--;
    }
    //向下统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        i++;
    }
    //向上统计
    i = x, j = y;
    while (a[i][j] != '#')//不是墙就可以继续
    {
        if (a[i][j] == 'G')
            sum++;
        i--;
    }
    return sum;
}

void dfs(int x, int y)
{
    int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
    sum = getnum(x, y);//统计当前点放置炸弹可以炸死多少敌人
    if (sum > max)    //更新当前最大值以及放置炸弹的位置
    {
        max = sum;
        mx = x;
        my = y;
    }
    for (int k = 0; k < 4; ++k) //枚举四个方向
    {
        int tx = x + next[k][0];
        int ty = y + next[k][1];
        if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1)  //不合法 旧尝试下一种情况
            continue;

        if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
        {
            book[tx][ty] = 1;                    //只是判断每个点，不用回溯
            dfs(tx, ty);
        }
    }
}
int main()
{
    cin >> n >> m >> startx >> starty;
    for (int i = 0; i <= n - 1; ++i)   //存入地图
        for (int j = 0; j <= m - 1; ++j)
            cin >> a[i][j];
    dfs(startx, starty);
    cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
    system("pause");
}

例2：宝岛探险，给出一幅n行m列的地图，其中0表示海洋，1到9表示陆地，求独立的岛屿个数。（即是求一个图中，独立的子图的个数）
输入示例：

10 10 
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

解法1：BFS解法，对岛屿进行着色，（觉得采用DFS比较好）

#include<iostream>

using namespace std;

int a[51][51]; //存储地图
int book[51][51]; //标记是否走过
int n, m;    //地图大小
struct note
{
    int x;
    int y;
};

int main()
{
    int color = 0;//对每个岛屿着色
    struct note que[2501]; //扩展队列 地图大小为50*50 扩展队列不会超过2501
    int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)  //读入地图
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    for (int i = 1; i <= n; ++i)                     //对每一个非0的点进行BFS
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] > 0)
            {
                --color;
                a[i][j] = color;    //进行染色
                int head = 1, tail = 1;      //入队
                que[head].x = i;
                que[head].y = j;
                tail++;
                book[i][j] = 1;
                while (head<tail)
                {
                    for (int k = 0; k < 4; ++k)      //遍历四个方向
                    {
                        int tx = que[head].x + next[k][0];
                        int ty = que[head].y + next[k][1];
                        if (tx<1 || tx>n || ty<1 || ty>m)   //判断边界是否满足
                            continue;

                        if (a[tx][ty] > 0 && book[tx][ty] == 0)
                        {
                            a[tx][ty] = color;     //入队前进行染色
                            que[tail].x = tx;
                            que[tail].y = ty;
                            tail++;
                            book[tx][ty] = 1;
                        }
                    }
                    head++;
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << "有" << -color << "个小岛";
    system("pause");
}

解法二：采用DFS，进行着色 （相比于BFS容易实现点）

#include<iostream>

using namespace std;

int a[51][51]; //存储地图
int book[51][51]; //标记是否走过
int n, m;    //地图大小
int color;
void dfs(int x, int y)
{
    int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
    a[x][y] = color;

    for (int k = 0; k < 4; ++k)      //遍历四个方向
    {
        int tx = x + next[k][0];
        int ty = y + next[k][1];
        if (tx<1 || tx>n || ty<1 || ty>m)   //判断边界是否满足
            continue;
        if (a[tx][ty] > 0 && book[tx][ty] == 0)
        {
            book[tx][ty] = 1;
            dfs(tx, ty);        //不用回溯
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)  //读入地图
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    for (int i = 1; i <= n; ++i)                     //对每一个非0的点进行BFS
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] > 0)
            {
                color--;
                dfs(i, j);
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << "有" << -color << "个小岛";
    system("pause");
}

例3：水管工游戏：（题目参考《啊哈算法》。。）

#include<iostream>

using namespace std;
int a[51][51];
int book[51][51], n, m,flag;

struct  note
{
    int x;
    int y;
}s[100];

int top = 0;
void dfs(int x,int y,int front)     //front 代表进水口方向
{
    if (x == n&&y == m + 1)
    {
        flag = 1;
        for (int i = 1; i <= top; ++i)
            cout << "("<<s[i].x << "," << s[i].y << ")" << " ";
        cout << endl;
        return;
    }
    if (x<1 || x>n || y<1 || y>m)
        return;

    if (book[x][y] == 1)
        return;

    book[x][y] = 1;
    top++;
    s[top].x = x;
    s[top].y = y;

    if (a[x][y] >= 5 && a[x][y] <= 6)   //为直管的情况
    {
        if (front == 1)    //进水口在左边
        {
            dfs(x, y + 1, 1);
        }

        if (front == 2)     //进水口在上边
        {
            dfs(x + 1, y, 2);
        }

        if (front == 3)     //进水口在右边
        {
            dfs(x, y-1, 3);
        }

        if (front == 4)     //进水口在下边边
        {
            dfs(x -1, y, 4);
        }
    }

    if (a[x][y] >= 1 && a[x][y] <= 4)     //为弯管的时候
    {
        if (front == 1)    //进水口在左边
        {
            dfs(x+1, y , 2);
            dfs(x-1 , y, 4);
        }

        if (front == 2)     //进水口在上边
        {
            dfs(x , y + 1, 1);
            dfs(x, y - 1, 3);
        }

        if (front == 3)     //进水口在右边
        {
            dfs(x+1, y , 2);
            dfs(x - 1, y, 4);
        }

        if (front == 4)     //进水口在下边
        {
            dfs(x, y + 1, 1);
            dfs(x, y - 1, 3);
        }
    }
    book[x][y] = 0;        //取消标记
    top--;                 //将当前尝试坐标出栈
    return;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    dfs(1, 1, 1);
    if (flag == 0)
        cout << "impossible" << endl;

    system("pause");
}