【代码随想录】【算法训练营】【第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 2500int 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;
}