Cactus Wall (Codeforces 1749E)
Tags: Others, shortest paths

Monocarp is playing Minecraft and wants to build a wall of cacti. He wants to build it on a field of sand of the size of $$$n \times m$$$ cells. Initially, there are cacti in some cells of the field. Note that, in Minecraft, cacti cannot grow on cells adjacent to each other by side — and the initial field meets this restriction. Monocarp can plant new cacti (they must also fulfil the aforementioned condition). He can't chop down any of the cacti that are already growing on the field — he doesn't have an axe, and the cacti are too prickly for his hands.Monocarp believes that the wall is complete if there is no path from the top row of the field to the bottom row, such that:   each two consecutive cells in the path are adjacent by side;  no cell belonging to the path contains a cactus. Your task is to plant the minimum number of cacti to build a wall (or to report that this is impossible).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$n \times m \le 4 \cdot 10^5$$$) — the number of rows and columns, respectively.Then $$$n$$$ rows follow, $$$i$$$-th row contains a string $$$s_i$$$ of length $$$m$$$, where $$$s_{i, j}$$$ is '#', if a cactus grows at the intersection of the $$$i$$$-th row and the $$$j$$$-th column. Otherwise, $$$s_{i, j}$$$ is '.'.The sum of $$$n \times m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output: For each test case, print NO in the first line if it is impossible to build a cactus wall without breaking the rules. Otherwise, print YES in the first line, then print $$$n$$$ lines of $$$m$$$ characters each — the field itself, where the $$$j$$$-th character of the $$$i$$$-th line is equal to '#', if there is a cactus on the intersection of the $$$i$$$-th row and the $$$j$$$-th column, otherwise it is '.'. If there are multiple optimal answers, print any of them.


Sample Inputs:
4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...

Sample Outputs:
YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v

def g(u):
    return (u // m, u % m)

def bfs():
    dist = [inf] * l
    q = [[] for _ in range(2)]
    (k, k0) = (0, 0)
    for i in range(0, l, m):
        if not ng[i]:
            dist[i] = s[i]
            q[dist[i]].append(i)
    parent = [-1] * l
    ma = 0
    for d in range(m + 1):
        q0 = q[d % 2]
        while len(q0) ^ k:
            u = q0[k]
            ma = max(ma, u % m)
            (i, j) = g(u)
            for (di, dj) in v2:
                (ni, nj) = (i + di, j + dj)
                if not 0 <= ni < n or not 0 <= nj < m:
                    continue
                v = f(ni, nj)
                if ng[v] or dist[v] ^ inf:
                    continue
                dist[v] = d + s[v]
                parent[v] = u
                q[dist[v] % 2].append(v)
            k += 1
        (k, k0) = (k0, k)
        if ma == m - 1:
            return (dist, parent)
    return (dist, parent)
t = int(input())
ans = []
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
v2 = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = pow(10, 9) + 1
for _ in range(t):
    (n, m) = map(int, input().split())
    l = n * m
    s = []
    ng = [0] * l
    for i in range(n):
        s0 = list(input().rstrip())
        for j in range(m):
            if s0[j] & 1:
                for (di, dj) in v:
                    (ni, nj) = (i + di, j + dj)
                    if not 0 <= ni < n or not 0 <= nj < m:
                        continue
                    ng[f(ni, nj)] = 1
        for j in s0:
            s.append(j & 1 ^ 1)
    (dist, parent) = bfs()
    mi = inf
    for i in range(m - 1, l, m):
        if mi > dist[i]:
            (mi, u) = (dist[i], i)
    if mi == inf:
        ans0 = 'NO'
        ans.append(ans0)
        continue
    s[u] = 0
    while not parent[u] == -1:
        u = parent[u]
        s[u] = 0
    ans0 = 'YES'
    ans.append(ans0)
    for i in range(n):
        ans0 = ['.' if s[j] else '#' for j in range(i * m, (i + 1) * m)]
        ans.append(''.join(ans0))
sys.stdout.write('\n'.join(ans))

Solution (Python):
from heapq import *
from collections import *
from functools import *
import os
from io import BytesIO, IOBase
import sys
import math
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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

def ReadInt():
    return int(input())

def ReadArray():
    return list(map(int, input().split()))

def solve():
    (H, W) = ReadArray()
    g = [list(input()) for i in range(H)]
    dist = [[math.inf for j in range(W)] for i in range(H)]
    found = False
    for i in range(H):
        for j in range(W):
            if g[i][j] != '#':
                continue
            if i > 0:
                dist[i - 1][j] = -1
            if j > 0:
                dist[i][j - 1] = -1
            if i < H - 1:
                dist[i + 1][j] = -1
            if j < W - 1:
                dist[i][j + 1] = -1
    q = deque()
    for i in range(H):
        if dist[i][0] != -1:
            if g[i][0] == '#':
                dist[i][0] = 0
                q.appendleft((i, 0))
            else:
                dist[i][0] = 1
                q.append((i, 0))
    parent = {}
    while q:
        (y, x) = q[0]
        q.popleft()
        for (yy, xx) in [(y + 1, x + 1), (y - 1, x + 1), (y + 1, x - 1), (y - 1, x - 1)]:
            if yy < 0 or xx < 0 or yy >= H or (xx >= W) or (dist[yy][xx] == -1):
                continue
            tempDist = dist[y][x] + int(g[yy][xx] != '#')
            if dist[yy][xx] == math.inf:
                if g[yy][xx] != '#':
                    q.append((yy, xx))
                else:
                    q.appendleft((yy, xx))
            if tempDist < dist[yy][xx]:
                dist[yy][xx] = tempDist
                parent[yy, xx] = (y, x)
    if all((dist[i][W - 1] == -1 or dist[i][W - 1] == math.inf for i in range(H))):
        print('NO')
        return
    else:
        print('YES')
    bestNode = -1
    minDist = math.inf
    for i in range(H):
        if dist[i][W - 1] == -1 or dist[i][W - 1] == math.inf:
            continue
        if dist[i][W - 1] < minDist:
            minDist = dist[i][W - 1]
            bestNode = i
    answer = []
    (y, x) = (bestNode, W - 1)
    while x != 0:
        g[y][x] = '#'
        (y, x) = parent[y, x]
    g[y][x] = '#'
    for el in g:
        print(''.join(el))
    return
    return

def main():
    for __ in range(ReadInt()):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import heapq

def trace_path(i, j, visited, grid):
    while j != 0:
        grid[i][j] = '#'
        (i, j) = visited[i][j]
    grid[i][j] = '#'
    for r in grid:
        print(''.join(r))

def solve():
    (n, m) = map(int, stdin.readline().split())
    grid = [list(stdin.readline().strip()) for i in range(n)]
    visited = [[None] * m for i in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '#':
                for (di, dj) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                    if 0 <= i + di < n and 0 <= j + dj < m:
                        visited[i + di][j + dj] = -1
    q = [(1 if grid[i][0] == '.' else 0, i, 0) for i in range(n) if visited[i][0] != -1]
    heapq.heapify(q)
    while q:
        (c, i, j) = heapq.heappop(q)
        if j == m - 1:
            print('YES')
            trace_path(i, j, visited, grid)
            return
        for (di, dj) in ((-1, -1), (-1, 1), (1, -1), (1, 1)):
            if 0 <= i + di < n and 0 <= j + dj < m and (not visited[i + di][j + dj]):
                visited[i + di][j + dj] = (i, j)
                heapq.heappush(q, (c + (grid[i + di][j + dj] == '.'), i + di, j + dj))
    print('NO')
for _ in range(int(stdin.readline())):
    solve()