leetcode-200. 岛屿数量

1. 题目

leetcode题目链接

2. 解答

思路：

1. 需要循环遍历每个节点；
2. 找到陆地，基于陆地开始遍历陆地的上下左右；
3. 数组dirm dirn就可以表示某个区域的上下左右；
4. 标记遍历过的节点；
5. 设计循环的退出条件；

#include <stdio.h>
#include <stdlib.h>int visited[300][300];
int dirm[] = {0, 0, 1, -1};
int dirn[] = {1, -1, 0, 0};int solve(int **data, int m, int n, int indexm, int indexn)
{if (indexm >= m || indexm < 0 || indexn >=n || indexn < 0) {return 0;}if (data[indexm][indexn] == 0 || visited[indexm][indexn] == 1) {return 0;}visited[indexm][indexn] = 1;int count = 1;for (int i = 0; i < 4; i++) {indexm += dirm[i];indexn += dirn[i];count += solve(data, m, n, indexm, indexn);}return count;}int main()
{int m, n;scanf("%d %d", &m, &n);if (m <= 0 || n < 0) return -1;int **data = malloc(sizeof(int *)*(m + 1));for (int i = 0; i < m; i++) {data[i] = malloc(sizeof(int) * (n+1));for (int j = 0; j < n; j++) {scanf("%d", &data[i][j]);visited[i][j] = 0;}}int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (visited[i][j] == 0 && data[i][j] == 1) {int result = 0;result +=solve(data, m, n, i, j);printf("小岛的大小:%d\n", result);count++;}}}printf("岛屿的个数:%d\n", count);for (int i = 0; i < m; i++) {free(data[i]);}free(data);return 0;
}

运行：

G3-3579:~/data/source/leetcode$ gcc 200.c
G3-3579:~/data/source/leetcode$ ./a.out 
4 5   
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
小岛的大小:4
小岛的大小:1
小岛的大小:2
岛屿的个数:3