比较简单的一题，考虑首先用dfs或者并查集预处理出每个点所在连通块的大小，再用个num把这个连通块标号。
对于每个点最后的答案，就是相邻4个点答案总和，不过需要注意的是可能会出现重复的情况，所以需要用一个pd数组表示在这次统计的时候这个连通块有没有出现过（num的作用），然后撤销不能memset而要重新遍历一遍，就可以通过了。
Code：
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1005
#define mod 998244353
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ld long double
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define SZ(x) (int)(x.size())
#define debug cout<<endl<<"ff"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define fi first
#define se second
#define INF 1e9
#define pq priority_queue
#define rep(x,a,b) for(int x=a;x<=b;x++)
int qpow(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1) res=res*a%mod;
a=a*a%mod;
}
return res;
}
/*int fac[N],ifac[N];
int C(int n,int m){
if(m>n||m<0||n<0) return 0;
return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
void init(){
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
ifac[N-1]=qpow(fac[N-1],mod-2);
for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}*/
/*struct node{
int nxt,to;
}e[N<<1];
int cnt=1,head[N];
inline void add(int x,int y){
e[++cnt].nxt=head[x];
head[x]=cnt;
e[cnt].to=y;
}*/
inline int lowbit(int x){return x&(-x);}
inline int read(){
int x=0,t=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x*t;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int T,n,m,a[N][N],col[N][N],vis[N][N],res[N*N],num,pd[N*N];
string s[N];
void dfs(int x,int y){
vis[x][y]=1;col[x][y]=num;res[num]++;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(nx<1||ny<1||nx>n||ny>m||vis[nx][ny]||s[nx][ny]=='*') continue;
dfs(nx,ny);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];s[i]=" "+s[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='*'||vis[i][j]) continue;
num++;dfs(i,j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='*'){
int sum=0;int x=i,y=j;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]=='*') continue;
if(pd[col[nx][ny]]) continue;
pd[col[nx][ny]]=1;sum+=res[col[nx][ny]];
}
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]=='*') continue;
pd[col[nx][ny]]=0;
}
cout<<(sum+1)%10;
}else cout<<".";
}
cout<<endl;
}
return 0;
}
aid：
#include <iostream>
#include <set>
using namespace std;
const int MAXN = 1005, gox[] = {-1, 0, 1, 0}, goy[] = {0, -1, 0, 1};
char c[MAXN][MAXN];
int p[MAXN * MAXN], ts[MAXN * MAXN];
int get(int x) {
return p[x] == x? x : p[x] = get(p[x]);
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if(x == y)
return;
if(ts[x] < ts[y])
swap(x, y);
ts[x] += ts[y];
p[y] = x;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> c[i];
for(int i = 0; i < n * m; i++) {
p[i] = i;
ts[i] = 1;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m - 1; j++)
if(c[i][j] == '.' && c[i][j + 1] == '.')
unite(i * m + j, i * m + j + 1);
for(int i = 0; i < n - 1; i++)
for(int j = 0; j < m; j++)
if(c[i][j] == '.' && c[i + 1][j] == '.')
unite(i * m + j, (i + 1) * m + j);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) {
if(c[i][j] == '.')
continue;
int cnt = 1;
set<int> st;
for(int d = 0; d < 4; d++) {
int x = i + gox[d], y = j + goy[d];
if(x < 0 || x >= n || y < 0 || y >= m || c[x][y] != '.')
continue;
int comp = get(x * m + y);
if(st.find(comp) != st.end())
continue;
cnt += ts[comp];
st.insert(comp);
}
c[i][j] = char('0' + (cnt % 10));
}
for(int i = 0; i < n; i++)
cout << c[i] << '\n';
return 0;
}
atetubou:
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define iter(a) __typeof(a.begin())
#define FOR(it,a) for(iter(a)it=a.begin();it!=a.end();++it)
#define F first
#define S second
#define SZ(a) (int)((a).size())
#define sz(a) SZ(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef unsigned long long ull;
#ifdef ONLINE_JUDGE
#define PR(...) (void(0))
#else
#define PR(...) do{cerr << "line : " << __LINE__ << ", " << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0)
template<class T>
void pr(const string& name, T t){
cerr << name << ": " << t << endl;
}
template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
auto p = names.find(',');
cerr << names.substr(0, p) << ": " << t << ", ";
pr(string(names, p + 1), rest ...);
}
#endif
template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}
template<class T,class U> ostream& operator<< (ostream& o, const map<T,U>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T,class U> ostream& operator<< (ostream& o, const unordered_map<T,U>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> ostream& operator<< (ostream& o, const set<T>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> string to_s(const T& v){ostringstream is;is << v;return is.str();}
const int dx[]={0,1,0,-1,1,1,-1,-1,0};
const int dy[]={1,0,-1,0,-1,1,1,-1,0};
#define endl '\n'
struct UnionFind{
/*
verified
size manipulation
http://mirror.codeforces.com/contest/516/submission/9910341
*/
vector<int> par, size;
vector<int> vis;
int vcnt;
int n;
UnionFind(int n):par(n), size(n), vis(n), vcnt(0), n(n){
init();
};
void init(){
++vcnt;
// fill(size.begin(), size.end(), 1);
// fill(par.begin(), par.end(), -1);
}
int find(int x){
if(vis[x] != vcnt){
vis[x] = vcnt;
par[x] = -1;
size[x] = 1;
}
if(par[x]==-1) return x;
return par[x] = find(par[x]);
}
bool unit(int a,int b){
int ap = find(a);
int bp = find(b);
if(ap == bp)
return false;
size[bp] += size[ap];
par[ap] = bp;
return true;
}
int& getsize(int a){
return size[find(a)];
}
};
int main(int argc, char *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> in(n);
rep(i, n) cin >> in[i];
UnionFind uf(n * m);
rep(i, n) rep(j, m){
if(in[i][j] == '*') continue;
rep(k, 4){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(in[nx][ny] == '.') uf.unit(i * m + j, nx * m + ny);
}
}
rep(i, n) rep(j, m){
if(in[i][j] == '.') continue;
map<int, int> app;
rep(k, 4){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(in[nx][ny] == '.') app[uf.find(nx * m + ny)] = uf.getsize(nx * m + ny);
}
int ans = 1;
for(auto e : app) ans += e.S;
in[i][j] = ans % 10 + '0';
}
rep(i, n) cout << in[i] << endl;
}