题意:给你一个地图,求联通块的数量。
题解:
for(所有还未标记的‘@’点)
边dfs边在vis数组标记id,直到不能继续dfs。
输出id及可;
ac代码:
#define _CRT_SECURE_NO_WARNINGS#include "stdio.h"#include<stdio.h>#include<algorithm>#include<string>#include<vector>#include<list>#include<set>#include<iostream>#include<string.h>#include<queue>#include<string>#include<sstream>using namespace std;const int maxn = 100+5;string map[maxn];int ans;int idx[maxn][maxn];int n, m;void dfs(int r,int c,int id) { if (r<0||c<0||r>=n||c>=m||map[r][c] == ‘*‘||idx[r][c])return; idx[r][c] = id; for(int dr=-1;dr<=1;dr++) for (int dc = -1; dc <= 1; dc++) if(dr||dc)dfs(r + dr, c + dc,id);}int main(){ while (cin >> n >> m) { if (n == 0 && m == 0)break; ans = 0; memset(idx, 0, sizeof(idx)); for (int i = 0; i < n; i++) { cin >> map[i]; } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (idx[i][j] == 0 && map[i][j] == ‘@‘) dfs(i, j, ++ans); cout << ans<<endl; } return 0;}