codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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).