303166: CF616C. The Labyrinth
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
The Labyrinth
题意翻译
给你一张图,‘*’表示墙,‘.’表示空地,问每个'*'周围的联通快中‘.’的数量和 mod 10,属于同一个联通快的只计算一次。题目描述
You are given a rectangular field of $ n×m $ cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '\*'. Let's call two empty cells adjacent if they share a side. Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component. For each impassable cell $ (x,y) $ imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains $ (x,y) $ . You should do it for each impassable cell independently. The answer should be printed as a matrix with $ n $ rows and $ m $ columns. The $ j $ -th symbol of the $ i $ -th row should be "." if the cell is empty at the start. Otherwise the $ j $ -th symbol of the $ i $ -th row should contain the only digit —- the answer modulo $ 10 $ . The matrix should be printed without any spaces. To make your output faster it is recommended to build the output as an array of $ n $ strings having length $ m $ and print it as a sequence of lines. It will be much faster than writing character-by-character. As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.输入输出格式
输入格式
The first line contains two integers $ n,m $ ( $ 1<=n,m<=1000 $ ) — the number of rows and columns in the field. Each of the next $ n $ lines contains $ m $ symbols: "." for empty cells, "\*" for impassable cells.
输出格式
Print the answer as a matrix as described above. See the examples to precise the format of the output.
输入输出样例
输入样例 #1
3 3
*.*
.*.
*.*
输出样例 #1
3.3
.5.
3.3
输入样例 #2
4 5
**..*
..***
.*.*.
*.*.*
输出样例 #2
46..3
..732
.6.4.
5.4.3