首页
课程
真题 题单
题库
书单 OI导航 直播 购买课程
修改密码

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

成品课程

陈远龙老师主讲 & 答疑

课程题单 - T1001

未购买 · 可先试学5节课

课程目录展开/折叠

第44课 图的实现与应用

视频 PPT&板书 讲课代码 课后练习
播放快捷键

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

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

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

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

本节课讲解到的源代码

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

1. C1136-红黑瓷砖-1 
#include <bits/stdc++.h>
using namespace std;

char mp[25][25];
bool vis[25][25];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int W, H; // W是列 H是行

int ans;

void dfs(int x, int y)
{
    vis[x][y] = true;
    ans ++;
    for (int d = 0; d < 4; d ++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if (mp[nx][ny] == '#') continue;
        if (vis[nx][ny]) continue;
        dfs(nx, ny);
    }
}

int main()
{

    while (cin >> W >> H)
    {
        if (W == 0 && H == 0) break;

        ans = 0;
        memset(mp, 0x00, sizeof(mp));
        memset(vis, 0x00, sizeof(vis));

        int xq, yq;
        for (int i = 0; i < H; i ++)
        {
            for (int j = 0; j < W; j ++)
            {
                cin >> mp[i][j];
                if (mp[i][j] == '@')
                {
                    xq = i;
                    yq = j;
                }
            }
        }

        dfs(xq, yq);
        cout << ans << endl;
    }

    return 0;
}
2. C1136-红黑瓷砖-2 
#include <bits/stdc++.h>
using namespace std;
/*
struct Point {
    int x;
    int y;
};
*/

char mp[25][25];
bool inq[25][25];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int W, H; // W是列 H是行

int ans;

void bfs(int x, int y)
{
    /*
    queue<Point> q;
    q.push({x, y});
    */
    queue<int> qx;
    queue<int> qy;
    qx.push(x);
    qy.push(y);
    inq[x][y] = true;

    while (!qx.empty())
    {
        int fx = qx.front();
        int fy = qy.front();
        ans ++;
        qx.pop();
        qy.pop();

        for (int d = 0; d < 4; d ++)
        {
            int nx = fx + dx[d];
            int ny = fy + dy[d];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (mp[nx][ny] == '#') continue;
            if (inq[nx][ny]) continue;

            qx.push(nx);
            qy.push(ny);
            inq[nx][ny] = true;
        }
    }

}

int main()
{
    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> W >> H)
    {
        if (W == 0 && H == 0) break;

        ans = 0;
        memset(mp, 0x00, sizeof(mp));
        memset(inq, 0x00, sizeof(inq));

        int xq, yq;
        for (int i = 0; i < H; i ++)
        {
            for (int j = 0; j < W; j ++)
            {
                cin >> mp[i][j];
                if (mp[i][j] == '@')
                {
                    xq = i;
                    yq = j;
                }
            }
        }

        bfs(xq, yq);
        cout << ans << endl;
    }

    return 0;
}
3. C1136-红黑瓷砖-3 
#include <bits/stdc++.h>
using namespace std;
struct point {
    int x;
    int y;
    point()
    {
        x = y = 0;
    }
    point(int i, int j)
    {
        x = i;
        y = j;
    }
};

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

char mp[100][100];
bool inq[100][100];
int m, n; // m行 n列

point q[1000];
int f, r;

void bfs(int i, int j)
{
    f = r = 0;
    point p1(i, j);
    q[r++] = p1;
    inq[i][j] = true;

    while (f != r)
    {
        point p = q[f];
        f ++;

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

            if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
            if (inq[ni][nj]) continue; // 不要重复入队
            if (mp[ni][nj] != '.') continue;

            point np(ni, nj);
            q[r++] = np;
            inq[ni][nj] = true;
        }
    }
}

int main()
{
    // cout << sizeof(mp) << endl;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0) break;

        memset(mp, 0x00, sizeof(mp));
        memset(inq, 0x00, sizeof(inq));
        int xq, yq;
        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                cin >> mp[i][j];
                if (mp[i][j] == '@')
                {
                    xq = i;
                    yq = j;
                }
            }
        }

        bfs(xq, yq); // 从xq,yq开始染色

        cout << r << endl; // 最后队列的大小就是联通块的大小        
    }

    /*
    // 下面也是一种求连通块大小的方法，变量inq数组，为true的代表被染色过了，染色过了就代表可以到达的黑色瓷砖 
    int cnt = 0;
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            if (inq[i][j] == true) cnt ++;
        }
    }
    cout << cnt << endl; 
    */

    return 0;
}
4. P1148-发现油田-1 
#include <bits/stdc++.h>
using namespace std;

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

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

// 从(x, y)这个点开始DFS
// 特征：dfs过的点，设置为* // 从(x, y)出发开始染色
void dfs(int x, int y)
{
    mp[x][y] = '*';

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

// 对所有的点进行DFS，全局染色
void dfs2()
{
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            if (mp[i][j] == '@')
            {
                ans ++;
                dfs(i, j);
            }

        }
    }
}

int main()
{
    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> m >> n)
    {
        if (m == 0) break;

        ans = 0;
        memset(mp, 0x00, sizeof(mp));

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

        dfs2();
        cout << ans << endl;

        /*
        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                dfs(i, j);
            }
        }
        */

    }

    return 0;
}
5. P1148-发现油田-2 
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    int y;
};

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

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

// 从一个点开始染色（遍历）
void bfs(int x, int y)
{
    queue<Point> q;
    q.push({x, y});
    // inq[x][y] = true; 不需要了
    mp[x][y] = '*';

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

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

            q.push({nx, ny});
            mp[nx][ny] = '*'; // 替代掉inq数组的作用
        }
    }

}

// 全局染色
void bfs2()
{
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            if (mp[i][j] == '@')
            {
                ans ++;
                bfs(i, j);
            }

        }
    }
}

int main()
{
    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> m >> n)
    {
        if (m == 0) break;

        ans = 0;
        memset(mp, 0x00, sizeof(mp));

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

        bfs2();
        cout << ans << endl;

    }

    return 0;
}
6. P1148-发现油田-3 
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    int y;
};

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

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

// 从一个点开始染色（遍历）
void bfs(int x, int y)
{
    queue<Point> q;
    q.push({x, y});
    inq[x][y] = true;
    // mp[x][y] = '*';

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

        for (int d = 0; d < 8; d ++)
        {
            int nx = p.x + dx[d];
            int ny = p.y + dy[d];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (mp[nx][ny] == '*') continue;
            if (inq[nx][ny]) continue;

            q.push({nx, ny});
            // mp[nx][ny] = '*'; // 替代掉inq数组的作用
            inq[nx][ny] = true;
        }
    }

}

// 全局染色
void bfs2()
{
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            if (mp[i][j] == '@' && inq[i][j] == false)
            {
                ans ++;
                bfs(i, j);
            }

        }
    }
}

int main()
{
    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> m >> n)
    {
        if (m == 0) break;

        ans = 0;
        memset(mp, 0x00, sizeof(mp));
        memset(inq, 0x00, sizeof(inq));

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

        bfs2();
        cout << ans << endl;

    }

    return 0;
}

本节课课后练习题

  1. C1136 - 红黑瓷砖数
  2. P1148 - 发现油田

本节课答疑

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

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

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

目录