天梯赛L2 - 048
开二维数组会编译失败,因此用string g[N]
来存,同时用于判重,节约空间。
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using PII = pair<int, int>;
const int N = 1e5 + 9;
int n, m;
string g[N];
int res1, res2;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
void bfs(int a, int b) {
bool tag = false;
queue<PII> q;
q.push({a, b});
if (g[a][b] >= '2') tag = true;
g[a][b] = '0'; // 节约空间
while (!q.empty()) {
PII f = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = f.x + dx[i], ny = f.y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '0') continue;
q.push({nx, ny});
if (g[nx][ny] >= '2') tag = true;
g[nx][ny] = '0'; // 节约空间
}
}
if (tag) res2++;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] != '0') {
res1++;
bfs(i, j);
}
}
}
cout << res1 << ' ' << res2;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}