题目描述
给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。
示例1
输入
[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
返回值
3
备注:
01矩阵范围<=200*200
题解
void dfs(int x, int y, vector<vector<char>> &grid, vector<vector<bool>> &mark, int height, int width) { if (x < 0 || y < 0 || x >= height || y >= width || mark[x][y] == false) { return; } if (grid[x][y] == '1') { mark[x][y] = false; dfs(x - 1, y, grid, mark, height, width); dfs(x + 1, y, grid, mark, height, width); dfs(x, y - 1, grid, mark, height, width); dfs(x, y + 1, grid, mark, height, width); } } /** * 判断岛屿数量 * @param grid char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector<char> >& grid) { // write code here if (grid.size() == 0) { return 0; } int width = grid[0].size(); int height = grid.size(); int count = 0; vector<vector<bool>> mark(height, vector<bool>(width, true)); for (int i = 0; i < height; ++i) { for (int j = 0; j < width; ++j) { if (grid[i][j] == '1' && mark[i][j] == true) { dfs(i, j, grid, mark, height, width); ++count; } } } return count; }