岛屿数量问题（C实现)

岛屿数量问题（C实现)"/>

岛屿数量问题（C实现)

岛屿数量问题，面试遇到，这里记录一下

题目是这样的

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

之前在网站上作答的时候，显示内存超出，我寻思32M内存应该够用了，今天在自己的环境测试后发现是网上找的代码里有错，所以记录一下

直接上代码

// An highlighted block
#include <stdio.h>char map[16][16];
int n, m;
int total;void GetMap() {scanf("%d%d\n", &n, &m);int i,j;for (i = 0; i < n; ++i) {for (j = 0; j < m; ++j) {scanf("%c", &map[i][j]);}getchar();}
}void Search(int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '0') {return;}map[x][y] = '0';Search(x - 1, y);Search(x, y - 1);Search(x, y + 1);Search(x + 1, y);
}void GetResult() {int i,j;for (i = 0; i < n; ++i) {for (j = 0; j < m; ++j) {if (map[i][j] == '1') {++total;Search(i, j);}}}
}int main()
{GetMap();GetResult();printf("%d\n", total);return 0;
}

刚才整理代码的时候发现，原来是我没有理解完全，写错了，那现在来整理一下思路
其实很简单。
1.函数 GetMap()循环读值，这就不用讲了。

2. 函数 GetResult()，这个函数就是循环遍历每个元素。

3. 函数 Search(int x, int y)， 这个函数就是在遍历到每个元素的时候，把上下左右相邻的岛屿， 修改成海水，然后记一块岛屿，这样统计就准确了。

   void Search(int x, int y) {
   if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == ‘0’) {
   return;
   }
   map[x][y] = ‘0’;
   Search(x - 1, y);
   Search(x, y - 1);
   Search(x, y + 1);
   Search(x + 1, y);
   }

如果写成map[x][y] = '2';if判断的时候就不会重复判断.
我之前错误在于没有彻底明白代码的意思，我写的是map[x][y] = ‘2’;这里修改成2 。在判断的时候又忽略了，所以会重复判断。
对这个错误的原因打个比方，map[0][0]判断完之后，会去判断map[0][1],在判断map[0][1]的时候，调用Search函数，又会回去重新判断map[0][0]。以此重复循环，最终段错误，如果把.map[0][0]的值改成2，就需要多一个判断条件，如果改成0则不需要。错在这里也比较可惜。
1 | 1

以上就是对这题的记录，思路，代码都是网上搜到的，自己遇到然后精炼了一下，记录下来，相关的还有岛屿的面积问题，最大面积，等。

参考链接

.html