连通块问题:时间复杂度O(n^2)

解题思路:连通块问题可以用dfs把每个不是0的位置修改为0，然后修改完成再遍历二维数组中下一个与任何1都不挨着的1，重复操作直到g[n-1][m-1]

注意事项:注意坐标偏移量问题

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;

int g[N][N];

void dfs(int x, int y) {

g[x][y] = 0;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

for (int i = 0; i < 4; i++) {

int a = x + dx[i], b = y + dy[i];

if (a >= 0 && a < n && b >= 0 && b < m && g[a][b]) {

dfs(a, b);

}

}

return;

}

int main() {

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

cin >> g[i][j];

int ans = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (g[i][j]) {

dfs(i, j);

ans++;

}

}

}

cout << ans << endl;

return 0;

}