直观上是一块块的面积和,想到并查集
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef pair<int, int> PII;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
//并查集
int n, m;
const int N = 1e6 + 7;
const int M = 1e3 + 7;
int p[N], cnt[N];
bool b[M][M];
int sum;
vector<vector<char>> a;
int idx(int x, int y) { // 将二维的坐标一维化
return x * 1000 + y;
}
int find(int x) { //找父节点
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int getsum(int x, int y) { //四个方向求总和 记得去重
int res = 0;
set<int> s;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
if (a[xx][yy] == '*') continue;
int pp = find(idx(xx, yy));
if (s.count(pp)) continue;
s.insert(pp);
res += cnt[pp];
}
}
return res;
}
void dfs(int x, int y) { //对每一个未曾访问的点搜索出它的所在区块
b[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == '.') {
if (!b[xx][yy]) {
int t1 = find(idx(x, y)), t2 = find(idx(xx, yy));
if (t1 != t2) //合并的同时加上个数
{
p[t2] = t1;
cnt[t1] += cnt[t2];
}
dfs(xx, yy);
}
}
}
}
void get_cnt() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (b[i][j])continue;
b[i][j] = true;
if (a[i][j] == '*') continue;
dfs(i, j);
}
}
}
int main()
{
ios::sync_with_stdio(false);
for (int i = 0; i < N; i++) cnt[i] = 1;
cin >> n >> m;
a = vector<vector<char>>(n, vector<char>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> a[i][j];
p[idx(i, j)] = idx(i, j); // 自己的父节点是自己
}
get_cnt();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) {
if (a[i][j] == '.') cout << '.';
else {
cout << (getsum(i, j) + 1) % 10;
}
}
cout << endl;
}
return 0;
}
为什么要去重
可能出现某一块包围了点的情况,如果不去重的话将出现重复计算
Orz
Orz
Orz
%%%%
orz