做网站标志有限颜色使用的吗,网站如何做宣传推广,wordpress网站测速,wordpress伪静态配置文件前言
思路及算法思维#xff0c;指路 代码随想录。 题目来自 卡码网。
day 58#xff0c;周四#xff0c;ding~
题目详情
[卡码102] 沉没孤岛
题目描述
卡码102 沉没孤岛
解题思路
前提#xff1a;修改孤岛的值 思路#xff1a;DFS or BFS#xff0c;使用visite…前言
思路及算法思维指路 代码随想录。 题目来自 卡码网。
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.hint 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;
}
今日收获
图的遍历DFS、BFS
