2 条题解
-
0
根据标签了解到了bfs(breadth first search, 广度优先)算法和dfs(depth first search, 深度优先)算法,个人认为先学深度优先再去学广度优先会更好,因为广度优先只需要在深度优先的基础上再改一下访问顺序就行了。我认为我的代码能给和我水平相近的人有所启发,故在此呈现我的题解:
深度优先算法:
#include <stdio.h> int n, m; char emo_matrix[105][105] = {0}; int visited_matrix[105][105] = {0}; int block_number = 0; void dfs(int x, int y) { visited_matrix[x][y] = 1; for (int k = -1; k <= 1; k ++) { for (int l = -1; l <= 1; l ++) { // k和l都为0就访问自己了 if (k != 0 || l != 0) { // 防止越界访问 if ( x + k >= 0 && x + k <= (n - 1) && y + l >= 0 && y + l <= (m - 1) ) { if (emo_matrix[x + k][y + l] == 'W' && visited_matrix[x + k][y + l] == 0) { dfs(x + k, y + l); } } } } } return; } int main(void) { scanf("%d %d\n", &n, &m); for (int i = 0; i < n; i ++) { // 不接收换行符 for (int j = 0; j < (m + 1); j ++) { char emo; scanf("%c", &emo); if (emo == '\n') { continue; } emo_matrix[i][j] = emo; } } for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { if (emo_matrix[i][j] == 'W' && visited_matrix[i][j] == 0) { dfs(i, j); // 递归结束,说明这一整块都被遍历了 block_number ++; } } } printf("%d", block_number); return 0; }
广度优先算法:
#include <stdio.h> int n, m; char emo_matrix[105][105] = {0}; int visited_matrix[105][105] = {0}; int block_number = 0; void bfs(int x, int y) { int neighbor[13][2] = {0}; for (int i = 0; i < 13; i ++) { neighbor[i][0] = -1; neighbor[i][1] = -1; } int counter = 0; for (int k = -1; k <= 1; k ++) { for (int l = -1; l <= 1; l ++) { if ( x + k >= 0 && x + k <= n && y + l >= 0 && y + l <= m ) { if (k != 0 || l != 0) { if (emo_matrix[x + k][y + l] == 'W' && visited_matrix[x + k][y + l] == 0) { visited_matrix[x + k][y + l] = 1; neighbor[counter][0] = x + k; neighbor[counter][1] = y + l; counter ++; } } } } } // 对邻居使用bfs() for (int i = 0; i < counter; i ++) { bfs(neighbor[i][0], neighbor[i][1]); } return; } int main(void) { scanf("%d %d\n", &n, &m); for (int i = 0; i < n; i ++) { for (int j = 0; j < (m + 1); j ++) { char emo; scanf("%c", &emo); // 不接收换行符 if (emo != '\n') { emo_matrix[i][j] = emo; } } } for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { if (emo_matrix[i][j] == 'W' && visited_matrix[i][j] == 0) { visited_matrix[i][j] = 1; bfs(i, j); block_number ++; } } } printf("%d", block_number); return 0; }
信息
- ID
- 170
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 403
- 已通过
- 209
- 上传者