利用递归实现DFS,解决并查集问题
岛屿数量
http://www.nowcoder.com/questionTerminal/0c9664d1554e466aa107d899418e814e
题目描述
给一个01矩阵,1代表是陆地,0代表海洋, 如果两个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
代码:
class Solution { public: /** * 判断岛屿数量 * @param grid char字符型vector<vector<>> * @return int整型 */ void dfs(int x, int y, const vector<vector<char> > &grid, vector<vector<bool> > &mark, int row, int col) { if (x < 0 || x >= row || y < 0 || y >= col || mark[x][y] == false) return; if (grid[x][y] == 1) { mark[x][y] = false; dfs(x - 1, y, grid, mark, row, col); dfs(x + 1, y, grid, mark, row, col); dfs(x, y - 1, grid, mark, row, col); dfs(x, y + 1, grid, mark, row, col); } } int solve(vector<vector<char> >& grid) { // write code here int row = grid.size(); if (row == 0) return 0; int col = grid[0].size(); int count = 0; vector<vector<bool> > mark(row, vector<bool>(col, true)); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (grid[i][j] == 1 && mark[i][j] == true) { dfs(i, j, grid, mark, row, col); ++count; } } } return count; } };