The Labyrinth (Codeforces 616C)
Tags: Others, dfs and similar

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.

Input: 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.

Output: Print the answer as a matrix as described above. See the examples to precise the format of the output.

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

Sample Inputs:
3 3
*.*
.*.
*.*

4 5
**..*
..***
.*.*.
*.*.*

Sample Outputs:
3.3
.5.
3.3

46..3
..732
.6.4.
5.4.3

Solution (Python):
import sys
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = [list(line.decode('utf-8').rstrip()) for line in sys.stdin.buffer]
group = [[0] * m for _ in range(n)]
size = [0]
gi = 1
for i in range(n):
    for j in range(m):
        if a[i][j] == '*' or group[i][j] != 0:
            continue
        stack = [(i, j)]
        cnt = 1
        group[i][j] = gi
        while stack:
            (y, x) = stack.pop()
            for (ty, tx) in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
                if 0 <= ty < n and 0 <= tx < m and (a[ty][tx] == '.') and (group[ty][tx] == 0):
                    group[ty][tx] = gi
                    stack.append((ty, tx))
                    cnt += 1
        size.append(cnt)
        gi += 1
for i in range(n):
    for j in range(m):
        if a[i][j] != '*':
            continue
        adj = set()
        for (ty, tx) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= ty < n and 0 <= tx < m and (a[ty][tx] == '.'):
                adj.add(group[ty][tx])
        res = 1
        for g in adj:
            res += size[g]
        a[i][j] = str(res)[-1]
sys.stdout.buffer.write('\n'.join((''.join(row) for row in a)).encode('utf-8'))

Solution (Python):
from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()

def inp():
    return sys.stdin.readline().rstrip('\r\n')

def ii():
    return int(inp())

def si():
    return str(inp())

def li(lag=0):
    l = list(map(int, inp().split()))
    if lag != 0:
        for i in range(len(l)):
            l[i] += lag
    return l

def mi(lag=0):
    matrix = list()
    for i in range(n):
        matrix.append(li(lag))
    return matrix

def lsi():
    return list(map(str, inp().split()))

def print_list(lista, space=' '):
    print(space.join(map(str, lista)))

def bisect_left(a, x):
    """"""
    left = 0
    right = len(a)
    while left < right:
        mid = (left + right) // 2
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid
    return left

def bisect_right(a, x):
    """"""
    left = 0
    right = len(a)
    while left < right:
        mid = (left + right) // 2
        if a[mid] > x:
            right = mid
        else:
            left = mid + 1
    return left

def bisect_elements(a, x):
    """"""
    return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
    return (x + y) % MOD

def multiply(x, y):
    return x * y % MOD

def power(x, y):
    if y == 0:
        return 1
    elif y % 2:
        return multiply(x, power(x, y - 1))
    else:
        a = power(x, y // 2)
        return multiply(a, a)

def inverse(x):
    return power(x, MOD - 2)

def divide(x, y):
    return multiply(x, inverse(y))

def allFactorials():
    FACT[0] = 1
    for i in range(1, maxN):
        FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
    n = len(INV_FACT)
    INV_FACT[n - 1] = inverse(FACT[n - 1])
    for i in range(n - 2, -1, -1):
        INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
    if n < k:
        return 0
    return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
    graph = [[] for i in range(n)]
    if unweighted:
        for i in range(m):
            [x, y] = li(lag=-1)
            graph[x].append(y)
            if undirected:
                graph[y].append(x)
    else:
        for i in range(m):
            [x, y, w] = li(lag=-1)
            w += 1
            graph[x].append([y, w])
            if undirected:
                graph[y].append([x, w])
    return graph

def create_tree(n, unweighted=1):
    children = [[] for i in range(n)]
    if unweighted:
        for i in range(n - 1):
            [x, y] = li(lag=-1)
            children[x].append(y)
            children[y].append(x)
    else:
        for i in range(n - 1):
            [x, y, w] = li(lag=-1)
            w += 1
            children[x].append([y, w])
            children[y].append([x, w])
    return children

def dist(tree, n, A, B=-1):
    s = [[A, 0]]
    (massimo, massimo_nodo) = (0, 0)
    distanza = -1
    v = [-1] * n
    while s:
        (el, dis) = s.pop()
        if dis > massimo:
            massimo = dis
            massimo_nodo = el
        if el == B:
            distanza = dis
        for child in tree[el]:
            if v[child] == -1:
                v[child] = 1
                s.append([child, dis + 1])
    return (massimo, massimo_nodo, distanza)

def diameter(tree):
    (_, foglia, _) = dist(tree, n, 0)
    (diam, _, _) = dist(tree, n, foglia)
    return diam

def dfs(graph, n, A):
    v = [-1] * n
    s = [[A, 0]]
    v[A] = 0
    while s:
        (el, dis) = s.pop()
        for child in graph[el]:
            if v[child] == -1:
                v[child] = dis + 1
                s.append([child, dis + 1])
    return v

def bfs(graph, n, A):
    v = [-1] * n
    s = deque()
    s.append([A, 0])
    v[A] = 0
    while s:
        (el, dis) = s.popleft()
        for child in graph[el]:
            if v[child] == -1:
                v[child] = dis + 1
                s.append([child, dis + 1])
    return v

def parents_children_root_unrooted_tree(tree, n, root=0):
    q = deque()
    visited = [0] * n
    parent = [-1] * n
    children = [[] for i in range(n)]
    q.append(root)
    while q:
        all_done = 1
        visited[q[0]] = 1
        for child in tree[q[0]]:
            if not visited[child]:
                all_done = 0
                q.appendleft(child)
        if all_done:
            for child in tree[q[0]]:
                if parent[child] == -1:
                    parent[q[0]] = child
                    children[child].append(q[0])
            q.popleft()
    return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
    q = deque()
    visited = [len(children[i]) for i in range(n)]
    downwards = [[0, 0] for i in range(n)]
    upward = [1] * n
    longest_path = [1] * n
    for i in range(n):
        if not visited[i]:
            q.append(i)
            downwards[i] = [1, 0]
    while q:
        node = q.popleft()
        if parent[node] != -1:
            visited[parent[node]] -= 1
            if not visited[parent[node]]:
                q.append(parent[node])
        else:
            root = node
        for child in children[node]:
            downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
    s = [node]
    while s:
        node = s.pop()
        if parent[node] != -1:
            if downwards[parent[node]][0] == downwards[node][0] + 1:
                upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
            else:
                upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
        longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
        for child in children[node]:
            s.append(child)
    return longest_path

def check(i, j, n, m):
    return i > -1 and j > -1 and (i < n) and (j < m)

def dfs_len(tab, i, j):
    d = [-1, 0, 1, 0, -1]
    n = len(tab)
    m = len(tab[0])
    stack = list()
    stack.append([i, j])
    visti[i][j] = 1
    count = 0
    while stack:
        (a, b) = stack.pop()
        count += 1
        for k in range(4):
            x = a + d[k]
            y = b + d[k + 1]
            if check(x, y, n, m) and tab[x][y] == '.' and (visti[x][y] == 0):
                visti[x][y] = 1
                par[x][y] = i * m + j
                stack.append([x, y])
    return count
(n, m) = li()
tab = list()
for i in range(n):
    tab.append(si())
visti = [[0 for i in range(m)] for j in range(n)]
par = [[-1 for i in range(m)] for j in range(n)]
le = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if tab[i][j] == '.' and visti[i][j] == 0:
            par[i][j] = i * m + j
            count = dfs_len(tab, i, j)
            le[i][j] = count
d = [-1, 0, 1, 0, -1]
res = [['.' for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if tab[i][j] != '.':
            count = 1
            parenti = list()
            for k in range(4):
                x = i + d[k]
                y = j + d[k + 1]
                if check(x, y, n, m):
                    p = par[x][y]
                    if p not in parenti:
                        parenti.append(p)
            for p in parenti:
                if p != -1:
                    yj = p % m
                    xi = p // m
                    count += le[xi][yj]
            res[i][j] = count % 10
for i in range(n):
    print_list(res[i], '')

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n

    def Find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.Find(self.par[x])
            return self.par[x]

    def Unite(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def Same(self, x, y):
        return self.Find(x) == self.Find(y)

    def Size(self, x):
        return -self.par[self.Find(x)]
import sys
import io, os
input = sys.stdin.readline
(n, m) = map(int, input().split())
S = [str(input().rstrip()) for i in range(n)]
uf = UnionFind(n * m)
for y in range(n):
    for x in range(m):
        if S[y][x] == '*':
            continue
        v = y * m + x
        for (dy, dx) in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            (ny, nx) = (y + dy, x + dx)
            if 0 <= ny < n and 0 <= nx < m and (S[ny][nx] == '.'):
                nv = ny * m + nx
                uf.Unite(v, nv)
ans = [['.'] * m for i in range(n)]
for y in range(n):
    for x in range(m):
        if S[y][x] == '.':
            continue
        v = y * m + x
        ps = set()
        for (dy, dx) in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            (ny, nx) = (y + dy, x + dx)
            if 0 <= ny < n and 0 <= nx < m and (S[ny][nx] == '.'):
                nv = ny * m + nx
                p = uf.Find(nv)
                ps.add(p)
        cnt = 1
        for p in ps:
            cnt += uf.Size(p)
        ans[y][x] = str(cnt % 10)
for y in range(n):
    print(''.join(ans[y]))