#include <bits/stdc++.h> using namespace std; char g[1010][1010]; int r, c, N, C[1010][1010], s[1010101], d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int dfs(int x, int y) { if (x < 0 || x >= r || y < 0 || y >= c || C[x][y] || g[x][y] == '') return 0; C[x][y] = N; int s = 1; for(int i=0;i<4;i++) s += dfs(x + d[i][0], y + d[i][1]); return s; } int main() { scanf("%d%d", &r, &c); for(int i=0;i<r;i++) scanf(" %s", g[i]); for(int i=0;i<r;i++) for(int j=0;j<c;j++) s[++N] = dfs(i, j); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) if (g[i][j] == '') { std::set::iterator it; set a; for(int k=0;k<4;k++) a.insert(C[i + d[k][0]][j + d[k][1]]); int z = 1; for (it=a.begin(); it!=a.end(); ++it) z += s[*it]; g[i][j] = '0' + (z % 10); } printf("%s\n", g[i]); } }

#include <bits/stdc++.h> using namespace std; char g[1010][1010]; int r, c, N, C[1010][1010], s[1010101], d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int dfs(int x, int y) { if (x < 0 || x >= r || y < 0 || y >= c || C[x][y] || g[x][y] == '') return 0; C[x][y] = N; int s = 1; for(int i=0;i<4;i++) s += dfs(x + d[i][0], y + d[i][1]); return s; } int main() { scanf("%d%d", &r, &c); for(int i=0;i<r;i++) scanf(" %s", g[i]); for(int i=0;i<r;i++) for(int j=0;j<c;j++) s[++N] = dfs(i, j); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) if (g[i][j] == '') { std::set::iterator it; set a; for(int k=0;k<4;k++) a.insert(C[i + d[k][0]][j + d[k][1]]); int z = 1; for (it=a.begin(); it!=a.end(); ++it) z += s[*it]; g[i][j] = '0' + (z % 10); } printf("%s\n", g[i]); } }

$30$ 分做法

从每个'*'出发开始 $dfs$ 。时间复杂度 $O(n^2m^2)​$ 。

$60$分做法：

从任何'.'出发都能到达任何'.'，所以如果一个'*'和'.'相邻，则'*'可以到达所有'.'。所以答案要么是1，要么是 $1+$ '.'的总数。

$100$ 分做法：

把'.'的所有连通块找出来，并统计每个连通块的大小，这可以通过 $O(nm)​$ 的 $dfs$ 实现。 然后对于每个'*'，看看它周围的'.'属于几个不同的连通块，答案就是 $1$ 加上周围所有连通块的大小之和。 时间复杂度 $O(nm)​$ 。

#include <bits/stdc++.h>
using namespace std;
char g[1010][1010];
int r, c, N, C[1010][1010], s[1010101], d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int x, int y) {
    if (x < 0 || x >= r || y < 0 || y >= c || C[x][y] || g[x][y] == '*') return 0;
    C[x][y] = N;
    int s = 1;
    for(int i=0;i<4;i++) s += dfs(x + d[i][0], y + d[i][1]);
    return s;
}
int main() {
    scanf("%d%d", &r, &c);
    for(int i=0;i<r;i++)
     scanf(" %s", g[i]);
    for(int i=0;i<r;i++)
    for(int j=0;j<c;j++) s[++N] = dfs(i, j);
    for(int i=0;i<r;i++) {
        for(int j=0;j<c;j++) if (g[i][j] == '*') {
            std::set<int>::iterator it;
            set<int> a;
            for(int k=0;k<4;k++) a.insert(C[i + d[k][0]][j + d[k][1]]);
            int z = 1;
            for (it=a.begin(); it!=a.end(); ++it) z += s[*it];
            g[i][j] = '0' + (z % 10);
        }
        printf("%s\n", g[i]);
    }
}