616C.md (2415B)
1 Source: https://codeforces.com/problemset/problem/616/C 2 3 C. The Labyrinth 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27 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. 28 29 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. 30 31 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. 32 33 Input 34 35 The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 1000) — the number of rows and columns in the field. 36 37 Each of the next *n* lines contains *m* symbols: "." for empty cells, "*" for impassable cells. 38 39 Output 40 41 Print the answer as a matrix as described above. See the examples to precise the format of the output. 42 43 Examples 44 45 Input 46 47 ``` 48 3 3 49 *.* 50 .*. 51 *.* 52 ``` 53 54 Output 55 56 ``` 57 3.3 58 .5. 59 3.3 60 ``` 61 62 Input 63 64 ``` 65 4 5 66 **..* 67 ..*** 68 .*.*. 69 *.*.* 70 ``` 71 72 Output 73 74 ``` 75 46..3 76 ..732 77 .6.4. 78 5.4.3 79 ``` 80 81 Note 82 83 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).