2663 水洼的大小

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

int n, m, Bcnt = 0; // Bcnt连通块的计数器
char a[maxn][maxn];
int vis[maxn][maxn]; // vis[i][j]表示(i,j)属于第几个连通块
int s[maxn]; // s[i]表示第i个连通块的大小

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
void dfs(int x, int y){
	vis[x][y] = Bcnt;
	s[Bcnt] ++;
	for(int i = 0; i < 4; i ++){
		int tx = x + dx[i], ty = y + dy[i];
		if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0 && a[tx][ty] == '.'){
			dfs(tx, ty);
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++) cin >> a[i][j];
	}
	
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(a[i][j] == '.' && vis[i][j] == 0){
				++ Bcnt; // 这样Bcnt从1开始
				dfs(i, j);
			}
		}
	}
	
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(a[i][j] == '.') cout << ".";
			else{
				vector <int> t(Bcnt + 1, 0); // t[i]表示是否访问过连通块i，避免(i,j)周围的多个点属于同一连通块，从而重复计算
				int tot = 1; // tot表示当前的答案。初始化为1是因为(i,j)也算作答案的一部分
				for(int k = 0; k < 4; k ++){
					int tx = i + dx[k], ty = j + dy[k];
					if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && t[vis[tx][ty]] == 0 && a[tx][ty] == '.'){
						t[vis[tx][ty]] = 1; // 打标记
						tot += s[vis[tx][ty]];
					}
				}
				cout << tot % 10;
			}
		}
		cout << "\n";
	}
	return 0;
}