首页 > 其他分享 >代码随想录第五十二天

代码随想录第五十二天

时间：2024-12-06 12:30:30浏览次数：7  
标签：int 代码 单元格 随想录 ++ grid 第五十二 nextx nexty

101.孤岛的总面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1

提示信息

在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。

数据范围：

1 <= M, N <= 50。

思路：

首先，我们从边界的陆地格子（值为1）开始，利用 DFS 将与之相连的所有陆地格子标记为已访问（通过将值改为0）。这样，我们就能确保所有与边界相连的陆地不会被算作内陆区域。接下来，我们继续在网格中查找其他的陆地区域，统计它们的面积。DFS 的作用是递归地遍历所有相连的陆地格子，并标记这些格子为访问过，避免重复计算。由于 DFS 是从边界的陆地格子开始的，所以所有的外部连通陆地区域都会被标记为已访问。最后，我们计算剩下的没有与边界相连的陆地区域的面积，作为答案输出。

解答：

#include <stdio.h>
#include <stdlib.h>

int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; 
int count; 

void dfs(int** grid, int x, int y, int n, int m) {
    grid[x][y] = 0; 
    count++; 
    for (int i = 0; i < 4; i++) { 
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
        if (grid[nextx][nexty] == 1) {
            dfs(grid, nextx, nexty, n, m);
        }
    }
    return;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int** grid = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = malloc(m * sizeof(int));
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0, n, m);
        if (grid[i][m - 1] == 1) dfs(grid, i, m - 1, n, m);
    }
    for (int j = 0; j < m; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j, n, m);
        if (grid[n - 1][j] == 1) dfs(grid, n - 1, j, n, m);
    }
    int connectedLand = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                connectedLand++;
            }
        }
    }
    printf("%d", connectedLand);
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);

    return 0;
}

102.沉没孤岛

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

提示信息

数据范围

1 <= M, N <= 50。

思路：

我们从网格的边界开始遍历，标记所有与边界相连的陆地格子。遍历过程中，每当我们发现一个陆地格子（值为1），我们就调用DFS函数，将与它相连的所有陆地格子都标记为访问过，并避免将它们当作内陆区域。首先，输入网格的大小并初始化网格数据，然后为每个格子分配内存并填充网格。接下来，我们使用一个新的网格 new_grid 来保存原始网格的拷贝，以便后续处理。在处理完所有的边界格子之后，调用DFS函数将所有与边界相连的陆地标记为0。接着，我们遍历网格，找出剩下的所有值为1的陆地，并调用DFS来统计连通区域的面积。最终，我们将内陆的陆地区域面积输出。

解答：

#include <stdio.h>
#include <stdlib.h>

int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; 
int count; 

void dfs(int** grid, int x, int y, int n, int m) {
    grid[x][y] = 0; 
    count++; 
    for (int i = 0; i < 4; i++) { 
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
        if (grid[nextx][nexty] == 1) {
            dfs(grid, nextx, nexty, n, m);
        }
    }
    return;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int** grid = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = malloc(m * sizeof(int));
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    int** new_grid = malloc(n*sizeof(int*));
    for(int i = 0;i < n;i++)
    {
        new_grid[i] = malloc(sizeof(int)*m);
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            new_grid[i][j] = grid[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0, n, m);
        if (grid[i][m - 1] == 1) dfs(grid, i, m - 1, n, m);
    }
    for (int j = 0; j < m; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j, n, m);
        if (grid[n - 1][j] == 1) dfs(grid, n - 1, j, n, m);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                new_grid[i][j] = 0;
            }
        }
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m-1;j++)
        {
            printf("%d ",new_grid[i][j]);
        }
        printf("%d\n",new_grid[i][m-1]);
    }
    return 0;
}

103.水流问题

题目描述

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

输入示例

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1

输出示例

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1

提示信息

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 100。

思路：

我们最开始初始化了两个二维布尔数组 first 和 second，这两个数组用来标记格子是否已经被访问过。然后，程序利用 dfs 函数从任意一个格子开始进行深度优先搜索。在 DFS 的过程中，程序检查当前格子的值和相邻格子的值。如果相邻格子的值小于当前格子的值，就停止进一步的递归，保证只遍历值较小的区域。递归会继续向上、下、左、右四个方向扩展，但每个格子只能被访问一次，因此使用 first 和 second 数组来确保每个格子只被遍历一次。DFS 的递归终止条件是所有可以遍历的格子都被访问过，或者某个方向的邻接格子的值不符合条件。最终我们就能打印出来最终答案。

解答：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int** graph = NULL;
bool** first = NULL;
bool** second = NULL;
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int** graph,bool** visited,int x,int y,int M,int N)
{
    if(visited[x][y])return;
    visited[x][y] = true;
    for(int i = 0;i < 4;i++)
    {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if(nextx < 0 || nextx >= M || nexty < 0 || nexty >= N)
        {
            continue;
        }
        if(graph[nextx][nexty] < graph[x][y])
        {
            continue;
        }
        dfs(graph,visited,nextx,nexty,M,N);
    }
}
int main()
{
    int M,N;
    scanf("%d %d",&N,&M);
    graph = malloc(sizeof(int*)*N);
    for(int i = 0;i < N;i++)
    {
        graph[i] = malloc(sizeof(int)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            scanf("%d",&graph[i][j]);
        }
    }
    first = malloc(sizeof(bool*)*N);
    for(int i = 0;i < N;i++)
    {
        first[i] = malloc(sizeof(bool)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            first[i][j] = false;
        }
    }
    second = malloc(sizeof(bool*)*N);
    for(int i = 0;i < N;i++)
    {
        second[i] = malloc(sizeof(bool)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            second[i][j] = false;
        }
    }
    for(int i = 0;i < N;i++)
    {
        dfs(graph,first,i,0,N,M);
        dfs(graph,second,i,M-1,N,M);
    }
    for(int i = 0;i < M;i++)
    {
        dfs(graph,first,0,i,N,M);
        dfs(graph,second,N-1,i,N,M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if(first[i][j] && second[i][j])
            {
                printf("%d %d\n",i,j);
            }
        }
    }
    return 0;
}

104.建造最大岛屿

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示最大的岛屿面积。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

6

提示信息

数据范围：

1 <= M, N <= 50。

思路：

每个岛屿是一个连通区域，我们可以通过 DFS 或 BFS 来遍历。当我们找到一个未访问过的陆地时，说明我们遇到了一个新的岛屿，于是从这个陆地开始进行 DFS 或 BFS，遍历该岛屿的所有陆地单元并计算岛屿的面积。在这个过程中，我们还需要为每个岛屿分配一个唯一的标识符，并记录每个岛屿的面积。接着，我们遍历每个水单元格（值为 0），对于每个水单元格，我们需要检查它周围四个方向是否有相邻的岛屿，如果有相邻岛屿，我们就将这些岛屿的面积加起来，得到将当前水单元格变为陆地后可能得到的岛屿面积。为了避免重复计算相邻的岛屿，我们需要使用一个集合来记录已经合并过的岛屿编号。在处理完所有水单元格后，我们得到一个新的岛屿面积，并与当前的最大岛屿面积进行比较，更新最大值。最终，当我们处理完所有水单元格后，得到的最大岛屿面积就是将一个水单元格变为陆地后，能够得到的最大岛屿面积。

解答：

#include <stdio.h>
#include <stdlib.h>

#define MAX 50
#define max(a, b) (a) > (b) ? (a) : (b)

int grid[MAX][MAX];

int N, M;

int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

void dfs(int x, int y, int** visited, int mark, int* cnt) {
    if (x < 0 || x >= N || y < 0 || y >= M) {
        return;
    }
    if (grid[x][y] == 0 || visited[x][y] == 1) {
        return;
    }
    visited[x][y] = 1;
    grid[x][y] = mark; 
    (*cnt)++;
    int i;
    for (i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        dfs(nextx, nexty, visited, mark, cnt);
    }
}

void bfs(int x, int y, int** visited, int mark, int* cnt) {
    int queue[N * M][2];
    int front = 0, rear = 0;
    visited[x][y] = 1;
    grid[x][y] = mark;
    (*cnt)++;
    queue[rear][0] = x;
    queue[rear++][1] = y;
    int i;
    while (front < rear) {
        int curx = queue[front][0];
        int cury = queue[front++][1];
        for (i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if ((nextx >= 0 && nextx < N) && (nexty >= 0 && nexty < M) && !visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                visited[nextx][nexty] = 1;
                grid[nextx][nexty] = mark;
                (*cnt)++;
                queue[rear][0] = nextx;
                queue[rear++][1] = nexty;
            }
        }
    }
}

int getsum(int x, int y, int* hash) {
    int sum = 0;
    int* repeat = malloc(N * M * sizeof(int));
    memset(repeat, 0, N * M * sizeof(int));
    int i;
    for (i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if ((nextx >= 0 && nextx < N) && (nexty >= 0 && nexty < M) && repeat[grid[nextx][nexty]] == 0) {
            sum += hash[grid[nextx][nexty]]; 
            repeat[grid[nextx][nexty]] = 1;  
        }
    }
    free(repeat);
    return sum;
}

int main() {
    
    scanf("%d %d", &N, &M);
    
    int i, j, k; 
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            scanf("%d", &(grid[i][j]));
        }
    }
    
    int** visited = malloc(N * sizeof(int*));
    for (i = 0; i < N; i++) {
        visited[i] = calloc(M, sizeof(int));
    }
    
    int* hash = calloc(N * M, sizeof(int));
    int mark = 2;
    int Allgrid = 1; 
    
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            int cnt = 0;
            if (grid[i][j] == 0) Allgrid = 0;
            if (grid[i][j] == 1 && !visited[i][j]) {
                bfs(i, j, visited, mark, &cnt);
                hash[mark] = cnt;
                mark++;
            }
        }
    }
    
    int result = 0;
    if (Allgrid) result = N * M;
    
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            if (grid[i][j] == 0) {
                int sum = 1; 
                sum += getsum(i, j, hash);
                result = max(result, sum);
            }
        }
    }
    
    printf("%d\n", result);
    
    for (i = 0; i < N; i++) {
        free(visited[i]);
    }
    free(visited);
    free(hash);
    
    return 0;
}

反思：

今天的题量有点大，我做了一早上，最后一道题还没做出来，需要重做，但是题目总体来说不是特别难，最重要的是你要知道它的思想，有了思想你就好做这些题了。

标签：int,代码,单元格,随想录,++,grid,第五十二,nextx,nexty
From： https://blog.csdn.net/2301_80630236/article/details/144288866

相关文章

  • 代码随想录第五十一天
    99.岛屿数量题目描述给定一个由1（陆地）和0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。输入描述第一行包含两个整数N,M，表示矩阵的行数和列数。后续N行，每行包含M个数字，数字为......
  • 使用requests包实现对网页HTML代码的获取
    在Python中，`requests`是一个非常流行的用于发送HTTP请求的库，它能够轻松获取网页的HTML代码。`requests`库的设计简洁易用，非常适合初学者和专业开发者使用。以下是如何使用`requests`包来获取网页HTML代码的详细步骤和示例。###1.安装`requests`包如果还没有安装`requests`......
  • git哪个操作会产生commit和将A分支的代码剪切到B分支
    git什么时候会产生commit在Git中，产生commit的操作主要是使用gitcommit命令。分支剪切有些时候，我们在A分支修改后代码，验证后发现没有问题在最后提交的时候发现，分支错误不是A分支，而是B分支这个时候我们不要把分支推送到远端而是切换到B分支，把commit号剪切过去然后切换到A分......
  • 判断如下边框的颜色，并解释为什么[代码]？
    请提供代码！我没有看到任何代码可以用来判断边框颜色。请把HTML和CSS代码贴出来，我会尽力帮你分析。我需要代码才能理解边框是如何定义的。它可能是内联样式、外部样式表或甚至是从JavaScript动态应用的。没有代码，我只能给出一些通用的方法：检查元素的style属性：如果边框......
  • 说说你对代码的可维护性的理解
    代码的可维护性对于前端开发至关重要，它直接影响项目的长期健康和开发团队的工作效率。高可维护性的代码更容易理解、修改、扩展和调试，从而降低开发成本，提高交付速度和质量。我的理解涵盖以下几个方面：1.可读性(Readability):清晰的代码结构:良好的代码组织，包括合理的目录......
  • 提交本地代码到git指定仓库
    1、找到本地代码的文件夹，在文件夹中右键鼠标，选择GitBash（前提是已经安装了Git） 2、执行以下命令 用来初始化文件 使用命令后 会出现.git文件gitinit3、指定源仓库地址  gitremoteaddoriginhttps://gitee.com/xxxx/yxxxx.git4、将本地项目设置为可提交状......
  • k-s检验代码
    https://blog.csdn.net/chehec2010/article/details/136991421?ops_request_misc=%257B%2522request%255Fid%2522%253A%25226cc12115b364e2a38467993f08a18139%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=6cc12115b364e2a38467993f08a18......
  • 如何实现前端代码实时预览效果？
    实现前端代码实时预览效果，有几种常见的方法：1.使用浏览器自带的开发者工具：这是最简单直接的方法，适用于简单的HTML、CSS和JavaScript修改。打开浏览器的开发者工具(通常是按下F12键)，在"元素"或"样式"面板中可以直接修改代码，并实时看到效果。对于JavaScript，可以在"控制......
  • springboot植物健康系统(代码+数据库+LW)
    摘要随着信息技术在管理上越来越深入而广泛的应用，管理信息系统的实施在技术上已逐步成熟。本文介绍了植物健康系统的开发全过程。通过分析植物健康系统管理的不足，创建了一个计算机管理植物健康系统的方案。文章介绍了植物健康系统的系统分析部分，包括可行性分析等，系统设计部分......
  • springboot学生评奖评优管理系统的设计与实现(代码+数据库+LW)
    摘要随着信息技术在管理上越来越深入而广泛的应用，管理信息系统的实施在技术上已逐步成熟。本文介绍了学生评奖评优管理系统的开发全过程。通过分析学生评奖评优管理系统管理的不足，创建了一个计算机管理学生评奖评优管理系统的方案。文章介绍了学生评奖评优管理系统的系统分析......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99