【代码随想录】【算法训练营】【第58天 2】 [卡码102]沉没孤岛

前言

思路及算法思维，指路 代码随想录。
题目来自 卡码网。

day 58，周四，ding~

题目详情

[卡码102] 沉没孤岛

题目描述

卡码102 沉没孤岛

解题思路

前提：修改孤岛的值
思路：DFS or BFS，使用visited代替直接修改grad的值
重点：DFS、BFS的实现

代码实现

C语言

DFS

// DFS

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

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

void dfs(int **grid, int gridSize, int *gridColSize, int colIdx, int rawIdx, bool **visited, bool *island, int *size, bool modify)
{
    // 退出条件
    if ((grid[colIdx][rawIdx] == 0) || ((modify == false) && (visited[colIdx][rawIdx] == true))) {
        return ;
    }
    
    // 递归
    visited[colIdx][rawIdx] = true;
    (*size)++;
    if (modify == true) {
        grid[colIdx][rawIdx] = 0;
    }
    if ((colIdx == 0) || (colIdx == (gridSize - 1)) || (rawIdx == 0) || (rawIdx == (gridColSize[colIdx] - 1))) {
        *island = true;
    }
    for (int k = 0; k < 4; k++) {
        int nextCol = colIdx + dir[k][0];
        int nextRaw = rawIdx + dir[k][1];
        // 越界
        if ((nextCol < 0) || (nextCol >= gridSize) || (nextRaw < 0) || (nextRaw >= gridColSize[nextCol])) {
            continue;
        }
        dfs(grid, gridSize, gridColSize, nextCol, nextRaw, visited, island, size, modify);
    }
    
    return ;
}

void sunkenIsland(int **grid, int gridSize, int *gridColSize)
{
    bool **visited = (bool **)malloc(sizeof(bool *) * gridSize);
    memset(visited, 0, sizeof(bool *) * gridSize);
    for (int n = 0; n < gridSize; n++) {
        visited[n] = (char *)malloc(sizeof(char) * gridColSize[n]);
        memset(visited[n], 0, sizeof(char) * gridColSize[n]);
    }
    bool island = false;
    int size = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            island = false;
            size = 0;
            dfs(grid, gridSize, gridColSize, i, j, visited, &island, &size, false);
            if ((island == false) && (size > 0)) {
                size = 0;
                dfs(grid, gridSize, gridColSize, i, j, visited, &island, &size, true);
            }
        }
    }
    for (int n = 0; n < gridSize; n++) {
        free(visited[n]);
        visited[n] = NULL;
    }
    free(visited);
    visited = NULL;
    return ;
}

int main()
{
    // 输入
    int n = 0;
    int m = 0;
    scanf("%d %d\n", &n, &m);
    int gridSize = n;
    int **grid = (int **)malloc(sizeof(int *) * gridSize);
    memset(grid, 0, sizeof(int *) * gridSize);
    int *gridColSize = (int *)malloc(sizeof(int) * gridSize);
    memset(gridColSize, 0, sizeof(int) * gridSize);
    for (int i = 0; i < gridSize; i++) {
        grid[i] = (int *)malloc(sizeof(int) * m);
        memset(grid[i], 0, sizeof(int) * m);
        gridColSize[i] = m;
        int count = 0;
        char ch = 0;
        while (((ch = getchar()) != '\n') && (count < m)) {
            if (ch == ' ') {
                continue;
            }
            grid[i][count++] = ch - '0';
        }
    }
    
    // 处理
    sunkenIsland(grid, gridSize, gridColSize);
    
    // 输出
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

BFS

// BFS

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

#define QUEUE_MAX_SIZE 2500

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

void bfs(int **grid, int gridSize, int *gridColSize, int colIdx, int rawIdx, bool **visited, bool *island, int *size, bool modify)
{
    // 退出条件
    if ((grid[colIdx][rawIdx] == 0) || ((modify == false) && (visited[colIdx][rawIdx] == true))) {
        return ;
    }
    
    // 队列
    int queue[QUEUE_MAX_SIZE][2];
    memset(queue, 0, sizeof(queue));
    int head = 0;
    int tail = 0;
    queue[tail][0] = colIdx;
    queue[tail][1] = rawIdx;
    tail++;
    visited[colIdx][rawIdx] = true;
    (*size)++;
    while (head != tail) {
        int curCol = queue[head][0];
        int curRaw = queue[head][1];
        head++;
        if (modify == true) {
            grid[curCol][curRaw] = 0;
        } else if ((curCol == 0) || (curCol == (gridSize - 1)) || (curRaw == 0) || (curRaw == (gridColSize[curCol] - 1))) {
            *island = true;
        }
        for (int k = 0; k < 4; k++) {
            int nextCol = curCol + dir[k][0];
            int nextRaw = curRaw + dir[k][1];
            // 越界
            if ((nextCol < 0) || (nextCol >= gridSize) || (nextRaw < 0) || (nextRaw >= gridColSize[nextCol])) {
                continue;
            }
            if ((grid[nextCol][nextRaw] == 0) || ((modify == false) && (visited[nextCol][nextRaw] == true))) {
                continue;
            }
            visited[nextCol][nextRaw] = true;
            queue[tail][0] = nextCol;
            queue[tail][1] = nextRaw;
            tail++;
            (*size)++;
        }
    }
    
    return ;
}

void sunkenIsland(int **grid, int gridSize, int *gridColSize)
{
    bool **visited = (bool **)malloc(sizeof(bool *) * gridSize);
    memset(visited, 0, sizeof(bool *) * gridSize);
    for (int n = 0; n < gridSize; n++) {
        visited[n] = (char *)malloc(sizeof(char) * gridColSize[n]);
        memset(visited[n], 0, sizeof(char) * gridColSize[n]);
    }
    bool island = false;
    int size = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            island = false;
            size = 0;
            bfs(grid, gridSize, gridColSize, i, j, visited, &island, &size, false);
            if ((island == false) && (size > 0)) {
                size = 0;
                bfs(grid, gridSize, gridColSize, i, j, visited, &island, &size, true);
            }
        }
    }
    for (int n = 0; n < gridSize; n++) {
        free(visited[n]);
        visited[n] = NULL;
    }
    free(visited);
    visited = NULL;
    return ;
}

int main()
{
    // 输入
    int n = 0;
    int m = 0;
    scanf("%d %d\n", &n, &m);
    int gridSize = n;
    int **grid = (int **)malloc(sizeof(int *) * gridSize);
    memset(grid, 0, sizeof(int *) * gridSize);
    int *gridColSize = (int *)malloc(sizeof(int) * gridSize);
    memset(gridColSize, 0, sizeof(int) * gridSize);
    for (int i = 0; i < gridSize; i++) {
        grid[i] = (int *)malloc(sizeof(int) * m);
        memset(grid[i], 0, sizeof(int) * m);
        gridColSize[i] = m;
        int count = 0;
        char ch = 0;
        while (((ch = getchar()) != '\n') && (count < m)) {
            if (ch == ' ') {
                continue;
            }
            grid[i][count++] = ch - '0';
        }
    }
    
    // 处理
    sunkenIsland(grid, gridSize, gridColSize);
    
    // 输出
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

今日收获

1. 图的遍历：DFS、BFS