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

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

成品课程

陈远龙老师主讲 & 答疑

课程题单 - T1001

未购买 · 可先试学5节课

课程目录展开/折叠

课程直播回放

第41课图的实现与应用

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

播放快捷键

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

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

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

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

本节课讲解到的源代码

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

1. P1145-扫雷游戏-1

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

char mp[105][105];
int n, m;

// 上、右上、右、右下、下、左下，左、左上（顺时针）
// 0, 1, 2, 3, 4, 5, 6, 7
// 硬编码
// 方向偏移数组
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            cin >> mp[i][j];
    }

    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            int t = 0; // 代表(i, j)周边的地雷数
            // i, j
            if (mp[i][j] == '*') cout << '*'; // 地雷格子
            else // if (mp[i][j] == '?') 非地雷格子
            {
                for (int d = 0; d < 8; d ++)
                {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    // 有效区间x: 0 ~ n - 1
                    // 有效区间y: 0 ~ m - 1
                    // 非法区间
                    if (ni < 0 || ni > n - 1 || nj < 0 || nj > m - 1) continue;

                    if (mp[ni][nj] == '*') t ++;
                }
                cout << t;

            }
        }
        cout << endl;
    }

    return 0;
}

2. P1145-扫雷游戏-2

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

char mp[105][105];
int n, m;

// 上、右上、右、右下、下、左下，左、左上（顺时针）
// 0, 1, 2, 3, 4, 5, 6, 7
// 硬编码
// 方向偏移数组
/*
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
*/
int di[2][8] = {
    {-1, -1, 0, 1, 1, 1, 0, -1},
    {0, 1, 1, 1, 0, -1, -1, -1}
};

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            cin >> mp[i][j];
    }

    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            int t = 0; // 代表(i, j)周边的地雷数
            // i, j
            if (mp[i][j] == '*') cout << '*'; // 地雷格子
            else // if (mp[i][j] == '?') 非地雷格子
            {
                for (int d = 0; d < 8; d ++)
                {
                    // int ni = i + dx[d];
                    // int nj = j + dy[d];
                    int ni = i + di[0][d];
                    int nj = j + di[1][d];
                    // 有效区间x: 0 ~ n - 1
                    // 有效区间y: 0 ~ m - 1
                    // 非法区间
                    // if (ni < 0 || ni > n - 1 || nj < 0 || nj > m - 1) continue;
                    // 有效区间判断
                    if (0 <= ni && ni < n && 0 <= nj && nj < m)
                    {
                        if (mp[ni][nj] == '*') t ++;
                    }
                }
                cout << t;

            }
        }
        cout << endl;
    }

    return 0;
}

3. C1132-迷宫最短路径-3

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

struct Point {
    int x;
    int y;
    int lid; // 当次节点所处的层次号，从1计数
};

// int ans[45][45]; // ans[x][y] 存储的就是(x, y)的层次号

char mp[45][45];

bool inq[45][45];

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

int r, c;
int x2, y2;

int bfs(int x, int y)
{
    queue<Point> q;
    // Point p(x, y);
    q.push({x, y, 1});
    inq[x][y] = true;

    while (!q.empty())
    {
        Point p = q.front();
        q.pop();

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

            if (nx == x2 && ny == y2)
            {
                // cout << "Found" << endl;
                // cout <<
                return p.lid + 1;
            }

            if (!inq[nx][ny])
            {
                q.push({nx, ny, p.lid + 1});
                inq[nx][ny] = true;
            }
        }

    }
    return -1;

}

int main()
{
    // int r, c;
    cin >> r >> c;
    for (int i = 1; i <= r; i ++)
    {
        for (int j = 1; j <= c; j ++)
        {
            cin >> mp[i][j];
        }
    }
    int x1, y1;
    cin >> x1 >> y1;
    // int x2, y2;
    cin >> x2 >> y2;

    if (mp[x1][y1] == '#' || mp[x2][y2] == '#')
    {
        cout << -1;
        return 0;
    }

    cout << bfs(x1, y1);

    return 0;
}

4. 1017 - C1132-迷宫最短路径

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

struct Point {
    int x;
    int y;
    int lever;
};

int r, c, x1, y1, x2, y2;
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool vis[50][50];
char m[50][50];

int bfs(int x, int y) {
    queue<Point> q;
    q.push({x, y, 1});
    vis[x][y] = true;
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = p.x + d[i][0], dy = p.y + d[i][1];
            if (dx < 0 || dx >= r || dy < 0 || dy >= c || m[dx][dy] == '#') continue;
            if (dx == x2 && dy == y2)
                return p.lever + 1;
            if (!vis[dx][dy]) {
                q.push({dx, dy, p.lever + 1});
                vis[dx][dy] = true;
            }
        }
    }
    return -1;
}

int main() {
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> m[i][j];

    cin >> x1 >> y1 >> x2 >> y2;
    x1--; y1--; x2--; y2--;

    if (m[x1][y1] == '#' || m[x2][y2] == '#') cout << -1;
    else cout << bfs(x1, y1);

    return 0;
}

本节课课后练习题

本节课答疑

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

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

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