【提升班·第2期】数据结构与算法C++语言描述

【2024课程】数据结构与算法C++语言描述课程

成品课程

陈远龙老师主讲 & 答疑

课程题单 - T1001

未购买 · 可先试学5节课

课程目录展开/折叠

课程直播回放

第42课图的实现与应用

视频 PPT&板书讲课代码课后练习

播放快捷键

播放/暂停：空格（或鼠标单击）全屏：F（或鼠标双击）退出全屏：Esc

快进10 / 30 / 60秒：方向键→ / Ctrl + 方向键→ / Shift + 方向键→

快退10 / 30 / 60秒：方向键← / Ctrl + 方向键← / Shift + 方向键←

本节课讲解配套PPT&板书：

本节课讲解到的源代码

源代码下载：第42课图的实现与应用-源代码下载

1. P1146-迷宫所有路径-1

#include <bits/stdc++.h>
using namespace std;

char mp[45][45];
int r, c;
int xq, yq;
int xz, yz;

// 上右下左 的方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool vis[45][45];
int ans;

void dfs(int x, int y)
{
    if (mp[x][y] == '#') return;

    if (x == xz && y == yz)
    {
        ans ++;
        return;
    }

    for (int d = 0; d < 4; d ++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        // nx: 1 - r ny: 1 - c
        if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
        if (mp[nx][ny] == '#') continue;
        if (vis[nx][ny]) continue;

        vis[nx][ny] = true;

        dfs(nx, ny);

        vis[nx][ny] = false;
    }
}

int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i ++)
    {
        for (int j = 1; j <= c; j ++)
            cin >> mp[i][j];
    }

    cin >> xq >> yq;
    cin >> xz >> yz;

    /*
    if (mp[xq][yq] == '#' || mp[xz][yz] == '#')
    {
        cout << 0;
        return 0;
    }
    */

    vis[xq][yq] = true;
    dfs(xq, yq);
    cout << ans;

    return 0;
}

2. P1146-迷宫所有路径-2

#include <bits/stdc++.h>
using namespace std;

char mp[45][45];
int r, c;
int xq, yq;
int xz, yz;

// 上右下左 的方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool vis[45][45];
int ans;

struct Point {
    int x;
    int y;
};

Point f[45 * 45]; // 方案数组、解向量
int k;

void dfs(int x, int y)
{
    // if (mp[x][y] == '#') return;

    if (x == xz && y == yz)
    {
        ans ++;
        for (int i = 0; i < k; i ++)
        {
            cout << "(" << f[i].x << "," << f[i].y << ") ";
        }
        cout << endl;

        return;
    }

    for (int d = 0; d < 4; d ++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        // nx: 1 - r ny: 1 - c
        if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
        if (mp[nx][ny] == '#') continue;
        if (vis[nx][ny]) continue;

        vis[nx][ny] = true;
        f[k++] = {nx, ny};

        dfs(nx, ny);

        vis[nx][ny] = false;
        k --;
    }
}

int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i ++)
    {
        for (int j = 1; j <= c; j ++)
            cin >> mp[i][j];
    }

    cin >> xq >> yq;
    cin >> xz >> yz;

    if (mp[xq][yq] == '#' || mp[xz][yz] == '#')
    {
        cout << 0;
        return 0;
    }

    f[k++] = {xq, yq};

    // vis[xq][yq] = true;
    dfs(xq, yq);
    cout << ans;

    return 0;
}

3. P1146-迷宫所有路径-3

#include <iostream>
using namespace std;

struct point {
    int x;
    int y;
};

int n, m;
char mg[100][100];
int xq, yq;
int xz, yz;

// int dx[] = {-1, 0, 1, 0};
// int dy[] = {0, 1, 0, -1};

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

point f[45 * 45]; // 方案数组

int ans;

void print(int k)
{
    for (int i = 1; i <= k; i ++)
    {
        cout << "(" << f[i].x << "," << f[i].y << ") " ;
    }
    cout << endl;
}

// 第k的解在第k - 1的基础上进行求解
void dfs(int k) // 尝试求第k的步，从第2步开始求解，当前步是在前一步的基础上进行求解的
{
    if (f[k - 1].x == xz && f[k - 1].y == yz) // 找到一个可行解
    {
        print(k - 1);
        ans ++;
        return;
    }

    for (int i = 0; i < 4; i ++)
    {
        // 尝试的新的坐标
        int nx = f[k - 1].x + dx[i];
        int ny = f[k - 1].y + dy[i];

        // 如果越界则跳过 合法的索引位置：1 <= x <= n  &&  1 <= y <= m
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;

        // 如果新坐标是个墙，则跳过
        if (mg[nx][ny] == '#') continue;

        f[k].x = nx;
        f[k].y = ny;

        mg[nx][ny] = '#'; // 当前坐标标识为不能走了，防止回头（死循环）

        dfs(k + 1);

        mg[nx][ny] = '.'; // 不是 mg[nx][ny] = '0';

    }
}

int main()
{
    /*
    char c;
    cin >> c; // 不会读入空白符的
    */

    cin >> n >> m;

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

    cin >> xq >> yq;
    cin >> xz >> yz;

    if (mg[xq][yq] == '#' || mg[xz][yz] == '#')
    {
        cout << 0;
        return 0;
    }

    // 初始状态，第1步的解，第1步的左边走过了，就不能走了
    f[1].x = xq;
    f[1].y = yq;
    mg[xq][yq] = '#'; // 是 # 和. 不是1和0

    dfs(2); // 从第2步开始求解

    cout << ans << endl;

    return 0;
}

本节课课后练习题

本节课答疑

建议大家有问题先通过AI答疑（比如：DeepSeek 等），AI时代需要学会使用AI辅助学习

陈远龙老师视频讲解：如何使用DeepSeek进行答疑？

通过AI未能获得满意解答的，可以联系陈远龙老师答疑