题干：

小O无意间发现了一张藏宝图，它跟随藏宝图的指引来到了一个宫殿，宫殿的地板被分成了n*m块格子，每个格子上放置了金子或者石头

藏宝图告诉小O，它可以选择一块石头变成金子，并且带走与变化后的金子联通区域的所有金子（联通指的是上下左右，不能斜着）

小O想计算一下点每个石头能带走的金子个数，帮帮他吧。

输入：
第一行两个数n,m (1 <= n,m <= 1000 )
随后n行，每行m个字符，表示宫殿地板上放置的物品，' * '表示放置的是石头，' . '表示放置的是金子

输出：
在每个石头位置输出如果将该位置点石成金，能带走的金子个数，方便起见，将这个数%10再输出

输入：
3 3
*.*
.*.
*.*
输出：
3.3
.5.
3.3

输入：
4 5
**..*
..***
.*.*.
*.*.*
输出：
46..3
..732
.6.4.
5.4.3
 

Note

In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

解题报告：

  搜索上并查集就可以了。注意统计的时候，有可能重复，比如

这样相同的答案会统计四次。所以要去重一下。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 1000 + 5;
char maze[MAX][MAX];
int ans[MAX][MAX];
bool vis[MAX][MAX];
int f[MAX*MAX];
int num[MAX*MAX]; 
int n,m;
int nx[4] = {0,1,0,-1};
int ny[4] = {1,0,-1,0};
int getf(int v) {
	return v == f[v] ? v : f[v] = getf(f[v]);
}
void merge(int u,int v) {
	int t1 = getf(u);
	int t2 = getf(v);
	f[t2] = t1;
}
int get(int x,int y) {
	return (x-1)*m +y;
}
void go(int x,int y) {
	for(int k = 0; k<4; k++) {
		int tx = x + nx[k];
		int ty = y + ny[k];
		if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
		if(maze[tx][ty] == '*' || vis[tx][ty]) continue;
		merge(get(x,y),get(tx,ty));
		vis[tx][ty] = 1;
		go(tx,ty);
	}
}
int main()
{
	cin>>n>>m;
	for(int i = 0; i<=n*m; i++) {
		f[i] = i;
	}
	for(int i = 1; i<=n; i++) {
		scanf("%s",maze[i]+1);
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=m; j++) {
			if(maze[i][j] == '.' && vis[i][j] == 0) {
				vis[i][j] = 1;
				go(i,j);
			}			
		}

	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=m; j++) {
			if(maze[i][j] == '*') continue;
			num[getf(get(i,j))]++;
		}
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=m; j++) {
			if(maze[i][j] == '.') ans[i][j] = '.';
			else {
				int cnt = 0;
				set<int> ss;
				for(int k = 0; k<4; k++) {
					int tx = i + nx[k];
					int ty = j + ny[k];
					if(maze[tx][ty] == '*')continue;
					if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
					ss.insert(getf(get(tx,ty)));
				}
				auto it = ss.begin();
				for(;it!=ss.end();++it) cnt += num[*it];
				ans[i][j] = cnt;
			}
		}
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=m; j++) {
			if(maze[i][j] == '.') printf(".");
			else printf("%d",(ans[i][j]+1)%10);
		}
		puts("");
	}
	return 0 ;
}
/*
16:00-16:13
*/
/*
4 1
*
.
*
.
*/

别忘了这样写的话，每个入口都要加上vis[][]=1;（指的是main函数里）

题目不难，但是还是WA了一发，映射的时候注意是(x-1)*m而不是(x-1)*n。