题目描述:
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例:
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
示例 2:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
解答描述:
一个非常典型的BFS广度优先搜索,求连通分量。
代码:
class Solution {
public:
void BFS(vector<vector<char>> &grid,int s,int t)
{
int d_x[4]={0,0,1,-1};
int d_y[4]={1,-1,0,0};
int rows=grid.size();
int cols=grid[0].size();
queue<pair<int,int>> q;
q.emplace(s,t);
grid[s][t]='2';
while(!q.empty())
{
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int new_x=x+d_x[i];
int new_y=y+d_y[i];
if(new_x>=0 && new_x<rows && new_y>=0 &&new_y<cols && grid[new_x][new_y]=='1')
{
q.emplace(new_x,new_y);
grid[new_x][new_y]='2';
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int rows=grid.size();
int cols=grid[0].size();
int islans=0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(grid[i][j]=='1')
{
islans++;
BFS(grid,i,j);
}
}
}
return islans;
}
};
题目描述:
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例:
解答描述:
该题可以把各个城市看做图的节点,城市之间的连线看做边,看做图的遍历,对每个节点,如果没有被访问过且有相邻的边的话,就深度遍历遍历下去。
代码
class Solution {
public:
void DFS(vector<vector<int>> & isConnected,vector<int> &visited,int s)
{
for(int i=0;i<isConnected.size();i++)
{
if(isConnected[s][i]==1 && !visited[i])
{
visited[i]=1;
DFS(isConnected,visited,i);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n=isConnected.size();
vector<int> visited(n,0);
int provinces=0;
for(int i=0;i<n;i++)
{
if(!visited[i])
{
visited[i]=1;
DFS(isConnected,visited,i);
provinces++;
}
}
return provinces;
}
};