夜静不堪题绝句
恐惊星斗落江寒
C++，连通图数量，dfs/bfs。
很常见的图论题，求连通图的数量，深搜和广搜都可以。
这里说一个很常用的技巧，是以前准备PAT看别人题解的时候学到的。
利用dx，dy实现四个方向的移位操作。
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
}
真的很好用！！！！
完整代码如下：
class Solution {
public:
int numIslands(vector<vector<char>> &grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
int ans = 0;
vector<vector<bool>> vis(m, vector<bool> (n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j] && grid[i][j] == '1') {
bfs(grid, vis, m, n, i, j);
ans++;
}
}
}
return ans;
}
void bfs(vector<vector<char>> &grid, vector<vector<bool>> &vis, int &m, int &n,
int x, int y) {
vis[x][y] = true;
queue<int> q;
q.push(x);
q.push(y);
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while (!q.empty()) {
x = q.front(); q.pop();
y = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (0 <= tx && tx < m && 0 <= ty && ty < n
&& !vis[tx][ty] && grid[tx][ty] == '1') {
q.push(tx);
q.push(ty);
vis[tx][ty] = true;
}
}
}
}
};
