Orac and Game of Life (Codeforces 1349C)
Tags: Implement, shortest paths

Please notice the unusual memory limit of this problem.Orac likes games. Recently he came up with the new game, "Game of Life".You should play this game on a black and white grid with $$$n$$$ rows and $$$m$$$ columns. Each cell is either black or white.For each iteration of the game (the initial iteration is $$$0$$$), the color of each cell will change under the following rules: If there are no adjacent cells with the same color as this cell on the current iteration, the color of it on the next iteration will be the same. Otherwise, the color of the cell on the next iteration will be different.Two cells are adjacent if they have a mutual edge.Now Orac has set an initial situation, and he wants to know for the cell $$$(i,j)$$$ (in $$$i$$$-th row and $$$j$$$-th column), what will be its color at the iteration $$$p$$$. He may ask you these questions several times. 

Input: The first line contains three integers $$$n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$$$, representing the number of rows, columns, and the number of Orac queries.Each of the following $$$n$$$ lines contains a binary string of length $$$m$$$, the $$$j$$$-th character in $$$i$$$-th line represents the initial color of cell $$$(i,j)$$$. '0' stands for white, '1' stands for black.Each of the following $$$t$$$ lines contains three integers $$$i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$$$, representing a query from Orac.

Output: Print $$$t$$$ lines, in $$$i$$$-th line you should print the answer to the $$$i$$$-th query by Orac. If the color of this cell is black, you should print '1'; otherwise, you should write '0'.

Note:   For the first example, the picture above shows the initial situation and the color of cells at the iteration $$$1$$$, $$$2$$$, and $$$3$$$. We can see that the color of $$$(1,1)$$$ at the iteration $$$1$$$ is black, the color of $$$(2,2)$$$ at the iteration $$$2$$$ is black, and the color of $$$(3,3)$$$ at the iteration $$$3$$$ is also black.For the second example, you can prove that the cells will never change their colors.

Sample Inputs:
3 3 3
000
111
000
1 1 1
2 2 2
3 3 3

5 2 2
01
10
01
10
01
1 1 4
5 1 4

5 5 3
01011
10110
01101
11010
10101
1 1 4
1 2 3
5 5 3

1 1 3
0
1 1 1
1 1 2
1 1 3

Sample Outputs:
1
1
1

0
0

1
0
1

0
0
0

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 998244353
dx = [[0, 1], [0, -1], [1, 0], [-1, 0]]
(n, m, t) = map(int, input().split())
a = [[int(i) for i in input()] for _ in range(n)]
d = []
dp = [[-1] * m for _ in range(n)]
timer = 0
for i in range(n):
    for j in range(m):
        for (x1, y1) in dx:
            x = i + x1
            y = j + y1
            if 0 <= x < n and 0 <= y < m and (a[i][j] == a[x][y]):
                dp[i][j] = 0
                d.append(i * m + j)
                break
while d:
    timer += 1
    nd = []
    for i1 in d:
        j = i1 % m
        i = i1 // m
        for (x1, y1) in dx:
            x = i + x1
            y = j + y1
            if 0 <= x < n and 0 <= y < m and (dp[x][y] == -1):
                dp[x][y] = timer
                nd.append(x * m + y)
    d = nd
for _ in range(t):
    (x, y, z) = map(int, input().split())
    x -= 1
    y -= 1
    if z < dp[x][y] or dp[x][y] == -1:
        print(a[x][y])
    else:
        nn = z - dp[x][y] & 1
        print(a[x][y] ^ nn)

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
import heapq as h, time
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
            self.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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
    return int(input())

def getStrs():
    return input().split()

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

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

def getBin():
    return list(map(int, list(input())))

def isInt(s):
    return '0' <= s[0] <= '9'

def ceil_(a, b):
    return a // b + (a % b > 0)
MOD = 10 ** 9 + 7
''

def solve():
    (N, M, T) = getInts()
    G = []
    for _ in range(N):
        G += getBin()
    size = N * M
    par = [-1] * size
    level = [-1] * size
    queue = dq([])

    def f(x):
        if x - M >= 0 and G[x - M] == G[x]:
            return True
        if x + M < size and G[x + M] == G[x]:
            return True
        if x % M and G[x - 1] == G[x]:
            return True
        if (x + 1) % M and G[x + 1] == G[x]:
            return True
        return False
    for i in range(N * M):
        if f(i):
            par[i] = G[i]
            level[i] = 0
            queue.append(i)
    while queue:
        node = queue.popleft()
        ops = []
        if node - M >= 0:
            ops.append(node - M)
        if node + M < size:
            ops.append(node + M)
        if node % M:
            ops.append(node - 1)
        if (node + 1) % M:
            ops.append(node + 1)
        for neigh in ops:
            if par[neigh] == -1:
                par[neigh] = par[node]
                level[neigh] = level[node] + 1
                queue.append(neigh)
    for _ in range(T):
        (i, j, p) = getInts()
        i -= 1
        j -= 1
        node = i * M + j
        if par[node] == -1:
            print(G[node])
        elif p < level[node]:
            print(G[node])
        else:
            print(par[node] ^ p % 2)
    return
solve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    (N, M, Q) = map(int, input().split())
    state = [list(input().rstrip()) for _ in range(N)]
    Query = [list(map(int, input().split())) for _ in range(Q)]
    Last = [[-1] * M for _ in range(N)]
    Need = [[-1] * M for _ in range(N)]
    q = []
    for n in range(N):
        for m in range(M):
            tmp = state[n][m]
            isStart = False
            if n != 0 and state[n - 1][m] == tmp:
                isStart = True
            if n != N - 1 and state[n + 1][m] == tmp:
                isStart = True
            if m != 0 and state[n][m - 1] == tmp:
                isStart = True
            if m != M - 1 and state[n][m + 1] == tmp:
                isStart = True
            if isStart:
                Need[n][m] = 0
                Last[n][m] = tmp - 48
                q.append((n, m))
    if not q:
        for (n, m, num) in Query:
            print(state[n - 1][m - 1] % 2)
    else:
        while q:
            qq = []
            for (n, m) in q:
                nexts = []
                if n != 0:
                    nexts.append((n - 1, m))
                if n != N - 1:
                    nexts.append((n + 1, m))
                if m != 0:
                    nexts.append((n, m - 1))
                if m != M - 1:
                    nexts.append((n, m + 1))
                for (pn, pm) in nexts:
                    if Last[pn][pm] == -1:
                        Last[pn][pm] = Last[n][m]
                        Need[pn][pm] = Need[n][m] + 1
                        qq.append((pn, pm))
            q = qq
        for (n, m, num) in Query:
            n -= 1
            m -= 1
            if num < Need[n][m]:
                print(state[n][m] % 2)
            else:
                print((Last[n][m] + num) % 2)
if __name__ == '__main__':
    main()