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

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

成品课程

陈远龙老师主讲 & 答疑

课程题单 - T1001

未购买 · 可先试学5节课

课程目录展开/折叠

课程直播回放

第43课图的实现与应用

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

播放快捷键

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

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

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

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

本节课讲解到的源代码

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

1. P1147-细胞的个数-1

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

struct Point {
    int x;
    int y;
};

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

int dx[] = {-1, 0, 1, 0}; // 上右下左
int dy[] = {0, 1, 0, -1};

// 局部的bfs，如果被bfs之后又什么特征 inq[x][y] = true
void bfs(int x, int y)
{
    queue<Point> q;
    q.push({x, y});
    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];

            // x: 0 - n -1  y : 0 - m - 1
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (mp[nx][ny] == '0') continue;
            if (inq[nx][ny]) continue;

            // cout << nx << ',' << ny << "  ";
            // cout << mp[nx][ny] << " ";
            q.push({nx, ny});
            inq[nx][ny] = true; // inqueue visited
        }
    }
}

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

    int ans = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            if (mp[i][j] != '0' && inq[i][j] == false)
            {
                ans ++;
                bfs(i, j);
                // cout << endl;
            }

        }
    }

    cout << ans;

    return 0;
}

2. P1147-细胞的个数-2

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

struct Point {
    int x;
    int y;
};

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

int dx[] = {-1, 0, 1, 0}; // 上右下左
int dy[] = {0, 1, 0, -1};

// 局部的bfs，如果被bfs之后又什么特征 inq[x][y] = true
void bfs(int x, int y)
{
    queue<Point> q;
    q.push({x, y});
    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];

            // x: 0 - n -1  y : 0 - m - 1
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (mp[nx][ny] == '0') continue;
            if (inq[nx][ny]) continue;

            // cout << nx << ',' << ny << "  ";
            // cout << mp[nx][ny] << " ";
            q.push({nx, ny});
            inq[nx][ny] = true; // inqueue visited
            mp[nx][ny] = '0';
        }
    }
}

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

    int ans = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            if (mp[i][j] != '0')
            {
                ans ++;
                bfs(i, j);
                mp[i][j] = '0';
            }

        }
    }

    cout << ans;

    return 0;
}

3. P1147-细胞的个数-3

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

struct Point {
    int x;
    int y;
};

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

int dx[] = {-1, 0, 1, 0}; // 上右下左
int dy[] = {0, 1, 0, -1};

int color[105][105];
int cid = 1; // color id

// 局部染色, cid, 局部的bfs，如果被bfs之后又什么特征 inq[x][y] = true
void bfs(int x, int y, int cid)
{
    queue<Point> q;
    q.push({x, y});
    inq[x][y] = true;

    while (!q.empty())
    {
        Point p = q.front();
        q.pop();
        color[p.x][p.y] = cid;

        for (int d = 0; d < 4; d ++)
        {
            int nx = p.x + dx[d];
            int ny = p.y + dy[d];

            // x: 0 - n -1  y : 0 - m - 1
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (mp[nx][ny] == '0') continue;
            if (inq[nx][ny]) continue;

            q.push({nx, ny});
            inq[nx][ny] = true; // inqueue visited
        }
    }
}

// 全局染色
void bfs2()
{

    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            if (mp[i][j] != '0' && color[i][j] == 0) bfs(i, j, cid++);
        }
    }
}

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

    bfs2();

    cout << cid - 1;

    /*
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            cout << color[i][j];
        cout << endl;
    }
    */

    return 0;
}

4. P1147-细胞的个数-4

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

struct Point {
    int x;
    int y;
};

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

int dx[] = {-1, 0, 1, 0}; // 上右下左
int dy[] = {0, 1, 0, -1};

int color[105][105];
int cid = 1; // color id

// 染色，局部染色
void dfs(int x, int y, int cid)
{
    // cout << mp[x][y];
    vis[x][y] = true;
    color[x][y] = cid;

    for (int d = 0; d < 4; d ++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (mp[nx][ny] == '0') continue;
        if (vis[nx][ny]) continue;

        dfs(nx, ny, cid);
    }

}

// 全局染色
void dfs2()
{
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            if (mp[i][j] != '0' && color[i][j] == 0) dfs(i, j, cid++);
        }
    }
}

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

    dfs2();
    cout << cid -1;

    return 0;
}

1022-迷宫最短路径-打印

#include <stdio.h>
#include <string.h>

int x[36], y[36], pre[36];
bool visit[6][6];
int head, tail;
int n = 5, m = 5, qx, qy, zx, zy;
int Map[6][6];

void print(int d) {
    if (pre[d] != 0) print(pre[d]);
    printf("(%d, %d)\n", x[d] - 1, y[d] - 1);
}

int bfs() {
    int dx[] = {0, 1, 0, -1};
    int dy[] = {-1, 0, 1, 0};
    memset(visit, 0, sizeof(visit));
    visit[qx][qy] = 1;
    tail++;
    x[tail] = qx, y[tail] = qy, pre[tail] = 0;
    while (head != tail) {
        head++;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x[head];
            int ny = dy[i] + y[head];
            if (nx > n || ny > m || nx < 1 || ny < 1) continue;
            if (Map[nx][ny]) continue;
            if (visit[nx][ny]) continue;
            tail++;
            x[tail] = nx, y[tail] = ny, visit[nx][ny] = 1, pre[tail] = head;
            if (nx == zx && ny == zy) {
                print(tail);
                printf("\n");
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            scanf("%d", &Map[i][j]);
        }
    }
    qx = qy = 1;
    zx = zy = 5;
    bfs();

    return 0;
}

本节课课后练习题

本节课答疑

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

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

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