万能的搜索

拼搏现实的明天。 2022-09-14 09:13 206阅读 0赞

## 不撞南墙不回头——深度优先搜索 ##

深度优先搜索（DFS）的基本模型

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

--------------------

假如有编号为 1，2，3 的3个盒子里，并且每个盒子有且只能 放一张扑克牌。  
那么有多少中不同的方法呢？

#include <stdio.h>
    int a[10], book[10], n;
    // C语言的全局变量在没有赋值以前默认为 0
    
    void dfs(int step){ 
        // step表示现在站在第几个盒子面前
        int i;
        if(step==n+1){ 
        //如果站在第 n+1个盒子面前，则表示前 n个盒子已经放好扑克牌
            for (i = 1; i <= n;i++)
            //输出一种排列（1~n号盒子中的扑克牌编号)
                printf("%d", a[i]);
            printf("\n");
            return;
            //返回之前的一步（最近依次调用 dfs函数的地方）
        }
        //此时站在第 step个盒子面前，应该放哪张牌呢？
        //按照 1，2，3...n的顺序尝试
        for (i = 1; i <= n;i++){ 
            //判断扑克牌 i是否还在手上
            if(book[i]==0){ 
                a[step] = i;
                //将 i号扑克牌放到第 step个盒子中
                book[i] = 1;
                //将 book[i]设为 1，表示 i号扑克牌已经不在手上 
                dfs(step + 1);
                book[i] = 0;
                //将刚才尝试的扑克牌收回，才能进行下一次尝试
            }
        }
        return;
    }
    
    int main(){ 
        scanf("%d", &n);
        // n为 1~9的整数
        dfs(1);
        //首先站在 1号小盒子面前
        getchar();
        getchar();
        return 0;
    }

--------------------

## 迷宫问题 ##

*  致敬 John E.Hopcroft 和 Robert E.Tarjan ！

#include <stdio.h>
    int n, m, p, q, min = 99999999;
    int a[51][51], book[51][51];
    void dfs(int x,int y,int step){ 
        int next[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
        int tx, ty, k;
        if(x==p&&y==q){ 
            //更新最小值
            if(step<min)
                min = step;
            return;
        }
        //枚举 4种走法
        for (k = 0; k <= 3;k++){ 
            //计算下一个点的坐标
            tx = x + next[k][0];
            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;
                    //尝试结束，取消这个点的标记
                }
        }
        return;
    }
    int main(){ 
        int i, j, startx, starty;
        scanf("%d %d", &n, &m);
        //读入迷宫
        for (i = 1; i <= n;i++){ 
            for (j = 1; j <= m;j++)
                scanf("%d", &a[i][j]);
            //读入起点和终点坐标
            scanf("%d %d %d %d", &startx, &starty, &p, &q);
            //从起点开始搜索
            book[startx][startx] = 1;
            //第一个参数是起点的 x坐标，第二个是起点 y的坐标，第三个是初始步数为0
            dfs(startx, starty, 0);
            printf("%d", min);
            getchar();
            getchar();
            return 0;
        }
    }

--------------------

## 层层递进——广度优先搜索 ##

BFS ，也称为 宽度优先搜索

#include <stdio.h>
    struct note{ 
        int x;
        int y;
        int f;
        int s;    //步数
    };
    
    int main(){ 
        struct note que[2501];
        int a[51][51] = { 0}, book[51][51] = { 0};
        //定义一个用于表示走的方向的数组
        int next[4][2] = { { (0, 1)}, { (1, 0)}, { (0, -1)}, { (-1, 0)}};
        int head, tail;
        int i, j, k, n, m, startx, starty, p, q, tx, ty, flag;
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n;i++)
            for (j = 1; j <= m;j++)
                scanf("%d %d %d %d", &startx, &starty, &p, &q);
        //队列初始化
        head = 1;
        tail = 1;
        //往队列插入迷宫入口坐标
        que[tail].x = startx;
        que[tail].y = starty;
        que[tail].f = 0;
        que[tail].s = 0;
        tail++;
        book[startx][starty] = 1;
        flag = 0;
        //用来标记是否到达目标点，0表示暂时还没有到达，1表示到达
        while(head<tail){ 
            for (k = 0; k <= 3;k++){ 
                //枚举4个方向
                tx = que[head].x + next[k][0];
                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;
                        que[tail].x = tx;
                        que[tail].y = ty;
                        que[tail].f = head;
                        que[tail].s = que[head].s + 1;
                        tail++;
                    }
                    //如果到目标点了，停止扩展，退出循环
                    if (tx == p && ty == q){ 
                        flag = 1;
                        break;
                    }
            }
            if(flag==1)
                break;
            head++;
            //当一个点扩展结束后，head++才能对后面的点再进行扩展
        }
        printf("%d", que[tail - 1].s);
        getchar();
        getchar();
        return 0;
    }

--------------------

## 再解炸弹人 ##

\[1\] 广度优先搜索

#include <stdio.h>
    struct note{ 
        int x;
        int y;
    };
    char a[20][21];
    
    int getnum(int i,int j){ 
        int sum, x, y;
        sum = 0;
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            x--;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            x++;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            y--;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            y++;
        }
        return sum;
    } 
    
    int main(){ 
        struct note que[401];
        int head, tail;
        int book[20][20] = { 0};
        int i, j, k, sum, max = 0, mx, my, m, n, startx, starty, tx, ty;
        int next[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
        scanf("%d %d %d %d", &n, &m, &startx, &starty);
        for (i = 0; i <= n - 1;i++)
            scanf("%s", a[i]);
        head = 1;
        tail = 1;
        que[tail].x = startx;
        que[tail].y = starty;
        tail++;
        book[startx][starty] = 1;
        max = getnum(startx, starty);
        mx = startx;
        my = starty;
        while(head<tail){ 
            for (k = 0; k >= 3;k++){ 
                tx = que[head].x + next[k][0];
                ty = que[head].y + next[k][1];
                if(tx<0||tx>n-1||ty<y||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++;
        }
        printf("将炸弹放置在(%d,%d)处，可以消灭%d个敌人\n", mx, my, max);
        getchar();
        getchar();
        return 0;
    }

--------------------

\[2\] 深度优先搜索

#include <stdio.h>
    char a[20][21];
    int book[20][20], max, mx, my, m, n;
    int getnum(int i,int j){ 
        int sum, x, y;
        sum = 0;
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            x--;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            x++;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            y--;
        }
        x = i;
        y = j;
        while(a[x][y]!='#'){ 
            if(a[x][y]=='G')
                sum++;
            y++;
        }
        return sum;
    }
    
    void dfs(int x,int y){ 
        int next[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
        int k, sum, tx, ty;
        sum = getnum(x, y);
        if(sum>max){ 
            max = sum;
            mx = x;
            mt = t;
        }
        for (k = 0; k <= 3;k++){ 
            tx = x + next[k][0];
            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);
                }
        }
        return;
    }
    
    int main(){ 
        int i, startx, starty;
        scanf("%d %d %d %d", &n, &m, &startx, &starty);
        for (i = 0; i <= n - 1;i++)
            scanf("%s", a[i]);
        book[startx][starty] = 1;
        max = getnum(startx, starty);
        mx = startx;
        my = starty;
        dfs(startx, starty);
        printf("将炸弹放置在(%d,%d)，最多可以消灭%d个敌人\n", mx, my, max);
        getchar();
        getchar();
        return 0;
    }

--------------------

## 宝岛探险 ##

\[1\] 广度优先搜索  
\[2\] 深度优先搜索  
\[3\] Floodfill 漫水填充法（种子填充法）

*  求一个图中独立子图的个数。
 *  具体的算法是：查找种子点周边的点，将与种子点颜色相近的点（可以设置一个阈值）入队作为新种子，并将新入队的种子也进行同样的扩展操作，这样就选取了和最初颜色相近颜色的区域。

#include <stdio.h>
    int a[51][51];
    int book[51][51], n, m, sum;
    
    void dfs(int x,int y,int color){ 
        int next[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
        int k, tx, ty;
        a[x][y] = color;
        for (k = 0; k <= 3;k++){ 
            tx = x + next[k][0];
            ty = y + next[k][1];
            if(tx<1||tx>n||ty<1||ty>m)
                continue;
                if(a[tx][ty]>0&&book[tx][ty]==0){ 
                    sum++;
                    book[tx][ty] = 1;
                    dfs(tx, ty, color);
                }
        }
        return;
    }
    
    int main(){ 
        int i, j, num = 0;
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n;i++)
            for (j = 1; j <= n;j++)
                scanf("%d", &a[i][j]);
        for (i = 1; i <= n;i++){ 
            for (j = 1; j <= m;j++){ 
                if(a[i][j]>0){ 
                    num--;
                    book[i][j] = 1;
                    dfs(i, j, num);
                }
            }
        }
        for (i = 1; i <= n;i++){ 
            for (j = 1; j <= m;j++){ 
                printf("%3d", a[i][j]);
            }
            printf("\n");
        }
        printf("有%d个小岛\n", -num);
        getchar();
        getchar();
        return 0;
    }

--------------------

## 水管工游戏 ##

#include <stdio.h>
    int a[51][51];
    int book[51][51], n, m, flag = 0;
    struct note{ 
        int x;
        int y;
    } s[100];
    int top;
    void dfs(int x,int y,int front){ 
        int i;
        if(x==n&&y==m+1){ 
            flag = 1;
            for (i = 1; i <= top;i++)
                printf("(%d,%d)", s[i].x, s[i], y);
            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, 4);
                    dfs(x, y - 1, 2);
                }
                if(front==4){ 
                    dfs(x, y + 1, 1);
                    dfs(x, y - 1, 3);
                }
            }
            book[x][y] = 0;
            top--;
            return;
    }
    
    int main(){ 
        int i, j, num = 0;
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n;i++)
            for (j = 1; j <= m;j++)
                scanf("%d", &a[i][j]);
        dfs(1, 1, 1);
        if(flag==0)
            printf("impossible\n");
        getchar();
        getchar();
        return 0;
    }

--------------------