此图片的alt属性为空;文件名为image-73.png

第一节.全排列——深度优先搜索思想

在树中,深度优先搜索策略是先选择某种情况尽可能深地搜索树,然后到达尽头后,再回到子结点改变条件,继续尽可能深地搜索,一般采用递归来实现。后面几章会进行更详细的介绍。

这一节主要是用这个思想解决全排列问题。比如要全排列1,2,3这三个数,先假定第一个数是1,第二个数是2,第三个数只能是3,此时到达尽头,回到"子结点"第二个数,将第二个数设为3,则第三个数只能是2......直到所有序列都排了一遍,完成全排列。

分析:需要book[i]来标记这几个数哪些已经用过了。可以用树来表示这个过程(下图),涉及递归,要把递归过程单独写一个函数。

此图片的alt属性为空;文件名为IMG_226620211109-211139-1024x567.jpg
  • 每一次递归中,找到一个还没使用过的数,使用并标记这个数
void dfs(int index){
    for (int i = 0; i < Size; i++)
        if (book[i] == 0) {      //说明这个数还没用过
            a[index] = i;       //使用这个数
            book[i]++;          //标记这个数已经用过
        }
}
  • 标记后,递归调用这个函数,进行下一个数的选择
void dfs(int index) {
    for (int i = 0; i < Size; i++)
        if (book[i] == 0) {      //说明这个数还没用过
            a[index] = i;       //使用这个数
            book[i]++;          //标记这个数已经用过
            dfs(index + 1);     //递归,进行下一个数的选择
        }
}
  • 关键:某次递归结束后,要把book[i]都重置为0,不然程序无法继续运行。
  • 比如Size=2(排列0,1)时,传入index=0,先执行for循环中i=0,a[0]=0,book[0]=1,递归:index=1,a[1]=1,book[1]=1,继续递归,index=2,此时满足结束条件,输出01退出递归。
  • 执行第二次for循环i=1,但由于此时book[0]和book[1]全为1,不满足book[i]==0,退出循环,程序结束。导致本来要输出的10没能输出。
void dfs(int index) {
    for (int i = 0; i < Size; i++)
        if (book[i] == 0) {       //说明这个数还没用过
            a[index] = i;         //使用这个数
            book[i]++;            //标记这个数已经用过
            dfs(index + 1); //递归,进行下一个数的选择
            book[i] = 0;          //关键:某次递归结束后,要把book[i]都重置为0,
        }
}
  • 递归结束条件
void dfs(int index) {
    for (int i = 0; i < Size; i++)
        if (book[i] == 0) {       //说明这个数还没用过
            a[index] = i;         //使用这个数
            book[i]++;            //标记这个数已经用过
            dfs(index + 1); //递归,进行下一个数的选择
            book[i] = 0;          //关键:某次递归结束后,要把book[i]都重置为0,
        }
    
    //递归结束条件
    if (index == Size) {           //说明本次排序结束
        for (int i = 0; i < Size; i++)     //输出序列
            printf("%d", a[i]);
        printf("\n");
        return;
    }
}

完整代码:

#include <stdio.h>

//假设全排序0到3这四个数字
#define Size 4

int a[Size];      //用来保存排序的数组
int book[Size];   //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0

void dfs(int index) {
    for (int i = 0; i < Size; i++)
        if (book[i] == 0) {       //说明这个数还没用过
            a[index] = i;         //使用这个数
            book[i]++;            //标记这个数已经用过
            dfs(index + 1); //递归,进行下一个数的选择
            book[i] = 0;          //关键:某次递归结束后,要把book[i]都重置为0,
        }

    //递归结束条件
    if (index == Size) {           //说明本次排序结束
        for (int i = 0; i < Size; i++)     //输出序列
            printf("%d", a[i]);
        printf("\n");
        return;
    }
}

int main() {
    dfs(0);
}

第二节.迷宫问题——深度优先搜索

本节主要介绍如何用上面说过的深度优先搜索思想求解迷宫的最短路径。

总体思路:递归传入每次所在的x、y坐标值以及目前所用步数(因为最后要选最短路径),判断:按顺时针(右、下、左、上)顺序尝试能不能走(障碍物或已经走过的点不能走),若能走,则标记该处走过,然后用调用递归函数的方法走向那里。

  • 二维数组构建迷宫,用1表示障碍物,用book[][]数组标记该点是否已经走过
//自定义迷宫大小
#define Sizex 5     //假设迷宫大小为5行4列
#define Sizey 4
//自定义开始位置
#define startx 1
#define starty 1
//自定义结束位置
#define endx 4
#define endy 3

//初始化上图那个五行四列的迷宫,两边用墙围起来,因此要+2
int a[Sizex+2][Sizey+2] = {{1,1,1,1,1,1},
                           {1,0,0,1,0,1},
                           {1,0,0,0,0,1},
                           {1,0,0,1,0,1},
                           {1,0,1,0,0,1},
                           {1,0,0,0,1,1},
                           {1,1,1,1,1,1}};
int book[Sizex+2][Sizey+2];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0
int road[100] ;              //一维数组保存这次遍历走的路
int min = 9999;              //用于和step对比,判断是否是最短路径

int main(){                               
    book[startx][starty] = 0;   //标记初始位置已经走过
    dfs(startx,starty,0);       //传入初始位置,初始步数为0
}
  • 为了便于编写往四个方向走的代码,我们可以定义以下的二维数组next。
  • 这样的话,往右走的坐标为tx=x+next[0][0],ty=y+next[0][1],往下走的坐标为tx=x+next[1][0],ty=y+next[1][1]......尝试往四个方向走的代码就可以用一个for循环来表示了。
int next[4][2] = {{0,1},    //往右走
                  {1,0},    //往下走
                  {0,-1},   //往左走
                  {-1,0}};  //往上走
//依次尝试四个方向
for(int k=0;k<4;k++){
            int tx = x+next[k][0];
            int ty = y+next[k][1];
        }
  • 判断是否下一步能不能走(障碍物或已经走过的点不能走),尝试走向下一步
//依次尝试四个方向
for(int k=0;k<4;k++){
    int tx = x+next[k][0];
    int ty = y+next[k][1];
    if(book[tx][ty]==0 && a[tx][ty]==0) {   //该处能走
        book[tx][ty] = 1;       //标记此处
        road[step*2] = tx;  //保存此处坐标
        road[step*2+1] = ty;
        dfs(tx, ty, step + 1);  //走向此处
        book[tx][ty] = 0;       //和上一节一样,递归结束要取消标记
    }
}
  • 递归结束条件:到达终点
//递归结束条件
if(x==endx && y==endy){
    //输出最短路径
    if(step < min) {
        min = step;
        printf("最少步数为:%d,最短路径如下:\n",min);
        for (int i=0;i<2*min;i=i+2) 
            printf("(%d,%d)\n",road[i],road[i+1]);
    }
    return;
}
  • 主函数:注意要先标注初始位置已经走过,book[startx][starty] = 0;
int main(){
    book[startx][starty] = 0;   //标记初始位置已经走过
    dfs(startx,starty,0);       //传入初始位置,初始步数为0
}

总代码:

#include <stdio.h>

//自定义迷宫大小
#define Sizex 5     //假设迷宫大小为5行4列
#define Sizey 4
//自定义开始位置
#define startx 1
#define starty 1
//自定义结束位置
#define endx 4
#define endy 3

//初始化上图那个五行四列的迷宫,两边用墙围起来,因此要+2
int a[Sizex+2][Sizey+2] = {{1,1,1,1,1,1},
                           {1,0,0,1,0,1},
                           {1,0,0,0,0,1},
                           {1,0,0,1,0,1},
                           {1,0,1,0,0,1},
                           {1,0,0,0,1,1},
                           {1,1,1,1,1,1}};
int book[Sizex+2][Sizey+2];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0
int road[100] ;              //一维数组保存这次遍历走的路
int min = 9999;              //用于和step对比,判断是否是最短路径

int next[4][2] = {{0,1},    //往右走
                  {1,0},    //往下走
                  {0,-1},   //往左走
                  {-1,0}};  //往上走

void dfs(int x,int y,int step){
    //依次尝试四个方向
    for(int k=0;k<4;k++){
        int tx = x+next[k][0];
        int ty = y+next[k][1];
        if(book[tx][ty]==0 && a[tx][ty]==0) {   //该处能走
            book[tx][ty] = 1;       //标记此处走过
            road[step*2] = tx;      //保存此处坐标
            road[step*2+1] = ty;
            dfs(tx, ty, step + 1);  //走向此处
            book[tx][ty] = 0;       //和上一节一样,递归结束要取消标记
        }
    }
    //递归结束条件
    if(x==endx && y==endy){
        //输出最短路径
        if(step < min) {
            min = step;
            printf("最少步数为:%d,最短路径如下:\n",min);
            for (int i=0;i<2*min;i=i+2)
                printf("(%d,%d)\n",road[i],road[i+1]);
        }
        return;
    }
}

int main(){
    book[startx][starty] = 0;   //标记初始位置已经走过
    dfs(startx,starty,0);       //传入初始位置,初始步数为0
}

运行结果:

第三节.迷宫问题——广度优先搜索

本节主要介绍用广度优先搜索思想求解迷宫的最短路径。

深度优先是通过递归实现的,而广度优先是通过队列实现的,它是通过一层一层往外扩展的办法,遍历所有位置。

比如下图,(1,1)进队后,(1,1)出队,假设我们仍采用右下左上顺时针的次序,(1,1)一步能到的(1,2),(2,1)依次进队,接着(1,2)出队,其一步能到的(2,3),(3,2)进队,接着(2,1)出队,其一步能到的(4,1)进队.....不断循环直到找到重点位置。

注意:广度优先找到的路径一定是最短的,因为一步一步扩散,循环条件是扩散到终点,其他能到终点的路径还没到就停止扩散了。

  • 因为用到队列,我们导入之前数据结构学过的队列里的那些操作。data域换成x坐标和y坐标以及步数step。
#define MaxSize Sizex*Sizey     //队列所需要的空间是迷宫格数

typedef int ElemType;
typedef struct {
    int x[Sizex];    //横坐标
    int y[Sizex];    //纵坐标
    int step[Sizex]; //步数
    int front, rear;        //队头和队尾指针
} SqQueue;

//初始化顺序队
void InitQueue(SqQueue *&q) {
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front = q->rear=-1;
}

//判断队列是否为空
bool QueueEmpty(SqQueue *q) {
    return (q->front==q->rear);
}

//进队
bool enQueue(SqQueue *&q, ElemType x,ElemType y) {
    if (q->rear==MaxSize-1)	//队满上溢出
        return false;
    q->rear++;
    q->x[q->rear] = x;
    q->y[q->rear] = y;
    return true;
}

//出队
bool deQueue(SqQueue *&q, ElemType &x, ElemType &y) {
    if (q->front==q->rear)	//队空
        return false;
    q->front++;
    x = q->x[q->front];
    y = q->y[q->front];
    return true;
}
  • 和深度优先一样,我们需要自定义并初始化迷宫、定义book数组标记已经扩展过的格子,next数组方便遍历下一步往四个方向走,此外我们还需要定义x、y、tx、ty变量分别来保存出队和入队元素的坐标
//自定义迷宫大小
#define Sizex 5     //假设迷宫大小为5行4列
#define Sizey 4
//自定义开始位置
#define startx 1
#define starty 1
//自定义结束位置
#define endx 4
#define endy 3

//初始化上图那个五行四列的迷宫,两边用墙围起来,因此要+2
int a[Sizex+2][Sizey+2] = {{1,1,1,1,1,1},
                           {1,0,0,1,0,1},
                           {1,0,0,0,0,1},
                           {1,0,0,1,0,1},
                           {1,0,1,0,0,1},
                           {1,0,0,0,1,1},
                           {1,1,1,1,1,1}};
int book[Sizex+2][Sizey+2];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0

int next[4][2] = {{0,1},    //往右走
                  {1,0},    //往下走
                  {0,-1},   //往左走
                  {-1,0}};  //往上走

int x, y;                   //保存出队位置的x坐标与y坐标
int tx, ty;                 //保存入队位置的x坐标和y坐标
  • 主函数里,首先,我们先定义并初始化一个空队,标记迷宫初始位置并将其进队
int main(){
    SqQueue * q;                //定义一个空队
    InitQueue(q);               //初始化空队
    book[startx][starty] = 1;   //标记初始位置已经走过
    enQueue(q,startx,starty);
}
  • 接着就是不断出队进队了,循环条件:队列不为空。依次遍历四个方向,将能走的位置入队。如果到终点,跳出循环。
  • 注:入队后,当前x、y及父亲位置分别对应q->x[q->rear],q->y[q->rear],q->f[q->rear],即这三个数组在位置上一一对应,如下图。
  • 父亲位置的下标即为头指针指向的位置,即q->f[q->rear] = q->front。该位置的步数=其父亲位置的步数+1,即q->step[q->rear] = q->step[q->front] + 1。
//循环条件:队列不为空
while(!QueueEmpty(q)){
    deQueue(q,x,y);     //将出队的位置坐标赋值给x、y
    //依次尝试四个方向
    for(int k=0;k<4;k++){
        tx = x+next[k][0];
        ty = y+next[k][1];
        if(book[tx][ty]==0 && a[tx][ty]==0) {   //该处能走
            book[tx][ty] = 1;       //标记此处
            enQueue(q,tx,ty);      //此处坐标入队
            q->f[q->rear] = q->front;   //父亲位置的下标即为头指针指向的位置
            q->step[q->rear] = q->step[q->front] + 1;   //该位置步数=父亲位置步数+1
        }
    }
    if(tx==endx && ty==endy)    //到达种点,跳出循环
        break;
}
  • 我们可以在判断条件里加上打印每次进队元素的信息,可以清楚地看到进队的过程
  • 最后,打印出路径。此时,front指向终点的前一个位置,我们想让front++,然后遍历每次的父亲位置,直到回到第一步,就找出这条路径。
q->front ++;
printf("最短步数为%d,路径为(反向):\n",q->step[q->front]);
for(;q->step[q->front]!=1; q->front = q->f[q->front])
    printf("(%d,%d)\n", q->x[q->front], q->y[q->front]);
printf("(%d,%d)\n", q->x[q->front], q->y[q->front]);

全部代码:

#include <stdio.h>
#include <cstdlib>

//自定义迷宫大小
#define Sizex 5     //假设迷宫大小为5行4列
#define Sizey 4
//自定义开始位置
#define startx 1
#define starty 1
//自定义结束位置
#define endx 4
#define endy 3

//导入队列运算的代码
#define MaxSize Sizex*Sizey     //队列所需要的空间是迷宫格数

typedef int ElemType;
typedef struct {
    int x[MaxSize];      //横坐标
    int y[MaxSize];      //纵坐标
    int step[MaxSize]; //步数
    int f[MaxSize];    //标记父亲位置在数组中的下标
    int front, rear;   //队头和队尾指针
} SqQueue;

//初始化顺序队
void InitQueue(SqQueue *&q) {
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front=q->rear=-1;
    q->step[0] = 0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue *q) {
    return (q->front==q->rear);
}

//进队
bool enQueue(SqQueue *&q, ElemType x,ElemType y) {
    if (q->rear==MaxSize-1)	//队满上溢出
        return false;
    q->rear++;
    q->x[q->rear] = x;
    q->y[q->rear] = y;
    return true;
}

//出队
bool deQueue(SqQueue *&q, ElemType &x, ElemType &y) {
    if (q->front==q->rear)	//队空
        return false;
    q->front++;
    x = q->x[q->front];
    y = q->y[q->front];
    return true;
}


//初始化上图那个五行四列的迷宫,两边用墙围起来,因此要+2
int a[Sizex+2][Sizey+2] = {{1,1,1,1,1,1},
                           {1,0,0,1,0,1},
                           {1,0,0,0,0,1},
                           {1,0,0,1,0,1},
                           {1,0,1,0,0,1},
                           {1,0,0,0,1,1},
                           {1,1,1,1,1,1}};
int book[Sizex+2][Sizey+2];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0

int next[4][2] = {{0,1},    //往右走
                  {1,0},    //往下走
                  {0,-1},   //往左走
                  {-1,0}};  //往上走

int x, y;                   //保存出队位置的x坐标与y坐标
int tx, ty;                 //保存入队位置的x坐标和y坐标

int main(){
    SqQueue * q;                  //定义一个空队
    InitQueue(q);              //初始化空队
    book[startx][starty] = 1;   //标记初始位置已经走过
    enQueue(q,startx,starty);   //迷宫初始位置进队

    //循环条件:队列不为空
    while(!QueueEmpty(q)){
        deQueue(q,x,y);     //将出队的位置坐标赋值给x、y
        //依次尝试四个方向
        for(int k=0;k<4;k++){
            tx = x+next[k][0];
            ty = y+next[k][1];
            if(book[tx][ty]==0 && a[tx][ty]==0) {   //该处能走
                book[tx][ty] = 1;       //标记此处
                enQueue(q,tx,ty);      //此处坐标入队
                q->f[q->rear] = q->front;   //父亲位置的下标即为头指针指向的位置
                q->step[q->rear] = q->step[q->front] + 1;   //该位置步数=父亲位置步数+1
            }
        }
        if(tx==endx && ty==endy)    //到达种点,跳出循环
            break;
    }
    
    //打印路径
    q->front ++;
    printf("最短步数为%d,路径为(反向):\n",q->step[q->front]);
    for(;q->step[q->front]!=1; q->front = q->f[q->front])
        printf("(%d,%d)\n", q->x[q->front], q->y[q->front]);
    printf("(%d,%d)\n", q->x[q->front], q->y[q->front]);
}

运行结果:

第四节.再解炸弹人游戏——深度或广度优先搜索

这一节主要介绍使用深度或广度优先搜索再去解 《啊哈!算法》:(三)枚举的第三节中炸弹人游戏,其原理和前两节解迷宫完全一致,只是需要遍历全部的位置加上统计杀敌数以及判断每个位置是否是最大杀敌数即可,这里就不再过多介绍了。

第五节.求解地图的小岛数

二维地图,0表示海洋,1-9表示陆地,多块连在一起的陆地即为一个小岛,要求地图上有多少个小岛。如图,有4个小岛。

总体思路:代码和第二节的代码非常像。我们可以用深度优先搜索,对每个大于0的点遍历,定义book数组标记已经遍历过的位置,定义一个color变量用于”染色“,-1表示第一个岛,-2表示第二个岛......

  • 初始化地图,和上面几个小节一样定义book数组用于标记,定义方向数组next
//初始化地图
int a[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}};

int book[10][10];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0

int next[4][2] = {{0,  1},    //往右走
                  {1,  0},    //往下走
                  {0,  -1},   //往左走
                  {-1, 0}};  //往上走
  • 递归函数dfs
  • 需要注意的是:判断条件要加上tx>=0 && ty>=0,否则会出现:比如tx=0,ty=-1(第一行最后一列的元素)和tx=0,ty=0在同一次遍历中,获得同样的染色,不是我们想要的。
  • 递归结束后不用像第二节的代码那样book[tx][ty] = 0初始化,初始化的原因是,我们不初始化只能进行一次遍历,不一定能覆盖所有点。然而我们主函数里传的是地图所有的点,每点都一定会被遍历到,所以不需要将book数组初始化。
void dfs(int x, int y, int color) {
    //对这个位置进行”染色“标记
    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>=0 && ty>=0 && book[tx][ty] == 0 && a[tx][ty] > 0) {
            book[tx][ty] = 1;       //标记此处遍历过
            dfs(tx, ty, color);     //尝试此处
        }
    }
}
  • 主函数。其实因为用深度搜索递归,我们主函数传入dfs(0,0,color)时,那一个小岛就全都标记成-1了,但是题目本意是我们不知道地图的信息,所以要遍历地图的某个点
int main() {
    int color = 0;  //用于”染色“
    //对每个>0的点尝试调用dfs函数进行然后
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++)
            if(a[i][j]>0)
            {
                color--;
                book[i][j] = 1;
                dfs(i,j,color);
            }
    }
    //输出”染色“后的地图
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++)
            printf("%3d",a[i][j]);
        printf("\n");
    }
}

总代码:

#include <stdio.h>

//初始化地图
int a[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}};

int book[10][10];  //说明:c语言全局变量没赋值时默认是0,因此无需初始化为0

int next[4][2] = {{0,  1},    //往右走
                  {1,  0},    //往下走
                  {0,  -1},   //往左走
                  {-1, 0}};   //往上走

void dfs(int x, int y, int color) {
    //对这个位置进行”染色“标记
    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>=0 && ty>=0 && book[tx][ty] == 0 && a[tx][ty] > 0) {
            book[tx][ty] = 1;       //标记此处遍历过
            dfs(tx, ty, color);     //尝试此处
        }
    }
}

int main() {
    int color = 0;  //用于”染色“
    //对每个>0的点尝试调用dfs函数进行然后
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++)
            if(a[i][j]>0)
            {
                color--;
                book[i][j] = 1;
                dfs(i,j,color);
            }
    }
    //输出”染色“后的地图
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++)
            printf("%3d",a[i][j]);
        printf("\n");
    }
}

运行结果:

第六节.水管工游戏

较难,之后再详细看。