You are given a 1×1×2$1 \times 1 \times 2$ bar (a cuboid) and a grid A$A$ with N$N$ rows (numbered 1$1$ through N$N$) and M$M$ columns (numbered 1$1$ through M$M$). Let's denote the cell in row r$r$ and column c$c$ by (r,c)$(r, c)$. Some cells of the grid are blocked, the remaining cells are free.
Each cell has dimensions 1×1$1 \times 1$, the same as two opposite faces of the cuboid. When the bar is placed on the grid in such a way that one of its two 1×1$1 \times 1$ faces fully covers a cell (r,c)$(r, c)$, we say that the bar is standing on the cell (r,c)$(r, c)$. Initially, the bar is standing on a cell (x,y)$(x, y)$.
When the bar is placed on the grid, one of its faces is touching the grid; this face is called the base. In one move, you must roll the bar over one of its base edges (sides of the base); this base edge does not move and the bar is rotated 90∘$90^\circ$ around it in such a way that it is still lying on the grid, but with a different base. In different moves, the bar may be rotated around different edges in different directions. After each move, the base of the bar must lie fully inside the grid and it must not cover any blocked cells.
An example sequence of moves is shown here.
For each cell of the grid, determine the minimum number of moves necessary to achieve the state where the bar is standing on this cell or determine that it is impossible to achieve.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and M$M$.
- The second line contains two space-separated integers x$x$ and y$y$.
- N$N$ lines follow. For each i$i$ (1≤i≤N$1 \le i \le N$), the i$i$-th of these lines contains M$M$ integers Ai,1,Ai,2,…,Ai,M$A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$ (a string with length M$M$). For each valid i,j$i, j$, Ai,j=0$A_{i, j} = 0$ denotes that the cell (i,j)$(i, j)$ is blocked and Ai,j=1$A_{i, j} = 1$ denotes that it is free.

-----Output-----
For each test case, print N$N$ lines, each containing M$M$ space-separated integers. For each valid i,j$i, j$, the j$j$-th integer on the i$i$-th of these lines should denote the minimum number of moves necessary to have the bar stand on cell (i,j)$(i, j)$, or it should be −1$-1$ if it is impossible.

-----Constraints-----
- 1≤T≤50$1 \le T \le 50$
- 1≤N,M≤1,000$1 \le N, M \le 1,000$
- 1≤x≤N$1 \le x \le N$
- 1≤y≤M$1 \le y \le M$
- 0≤Ai,j≤1$0 \le A_{i, j} \le 1$ for each valid i,j$i, j$
- Ax,y=1$A_{x, y} = 1$
- the sum of N⋅M$N \cdot M$ over all test cases does not exceed 106$10^6$

-----Subtasks-----
Subtask #1 (15 points):
- x=1$x = 1$
- y=1$y = 1$
- Ai,j=1$A_{i, j} = 1$ for each valid i,j$i, j$
Subtask #2 (85 points): original constraints

-----Example Input-----
2
2 4
1 1
1111
0111
2 4
1 1
1111
0011

-----Example Output-----
0 -1 -1 2
-1 -1 -1 3
0 -1 -1 2
-1 -1 -1 -1

-----Explanation-----
Example case 1: Initially, the base of the bar occupies the cell (1,1)$(1, 1)$. After the first move, it occupies the cells (1,2)$(1, 2)$ and (1,3)$(1, 3)$. After the second move, it can occupy the cell (1,4)$(1, 4)$.
Alternatively, after the second move, it can occupy the cells (2,2)$(2, 2)$ and (2,3)$(2, 3)$, and after the third move, it can occupy the cell (2,4)$(2, 4)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
def issafe(r, c, r1, c1, graph):
	if graph[r][c] and graph[r1][c1]:
		return True
	return False
t = int(input())
for mmmmmm in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	graph = [[False] * (m + 2) for _ in range(n + 2)]
	cost_graph = [[[-1, -1, -1] for __ in range(m)] for _ in range(n)]
	for i in range(n):
		str1 = input()
		for (j, val) in enumerate(str1):
			graph[i][j] = val == '1'
	x = x - 1
	y = y - 1
	set1 = set()
	set1.add((x, y, 0))
	cost_graph[x][y][0] = 0
	while set1:
		set2 = set()
		while set1:
			(r, c, p) = set1.pop()
			new_cost = cost_graph[r][c][p] + 1
			if p == 0:
				if issafe(r, c + 1, r, c + 2, graph):
					if cost_graph[r][c + 1][1] == -1 or cost_graph[r][c + 1][1] > new_cost:
						cost_graph[r][c + 1][1] = new_cost
						set2.add((r, c + 1, 1))
				if issafe(r + 1, c, r + 2, c, graph):
					if cost_graph[r + 1][c][2] == -1 or cost_graph[r + 1][c][2] > new_cost:
						cost_graph[r + 1][c][2] = new_cost
						set2.add((r + 1, c, 2))
				if issafe(r, c - 2, r, c - 1, graph):
					if cost_graph[r][c - 2][1] == -1 or cost_graph[r][c - 2][1] > new_cost:
						cost_graph[r][c - 2][1] = new_cost
						set2.add((r, c - 2, 1))
				if issafe(r - 2, c, r - 1, c, graph):
					if cost_graph[r - 2][c][2] == -1 or cost_graph[r - 2][c][2] > new_cost:
						cost_graph[r - 2][c][2] = new_cost
						set2.add((r - 2, c, 2))
			elif p == 1:
				if issafe(r, c + 2, r, c + 2, graph):
					if cost_graph[r][c + 2][0] == -1 or cost_graph[r][c + 2][0] > new_cost:
						cost_graph[r][c + 2][0] = new_cost
						set2.add((r, c + 2, 0))
				if issafe(r + 1, c, r + 1, c + 1, graph):
					if cost_graph[r + 1][c][1] == -1 or cost_graph[r + 1][c][1] > new_cost:
						cost_graph[r + 1][c][1] = new_cost
						set2.add((r + 1, c, 1))
				if issafe(r, c - 1, r, c - 1, graph):
					if cost_graph[r][c - 1][0] == -1 or cost_graph[r][c - 1][0] > new_cost:
						cost_graph[r][c - 1][0] = new_cost
						set2.add((r, c - 1, 0))
				if issafe(r - 1, c, r - 1, c + 1, graph):
					if cost_graph[r - 1][c][1] == -1 or cost_graph[r - 1][c][1] > new_cost:
						cost_graph[r - 1][c][1] = new_cost
						set2.add((r - 1, c, 1))
			elif p == 2:
				if issafe(r, c + 1, r + 1, c + 1, graph):
					if cost_graph[r][c + 1][2] == -1 or cost_graph[r][c + 1][2] > new_cost:
						cost_graph[r][c + 1][2] = new_cost
						set2.add((r, c + 1, 2))
				if issafe(r + 2, c, r + 2, c, graph):
					if cost_graph[r + 2][c][0] == -1 or cost_graph[r + 2][c][0] > new_cost:
						cost_graph[r + 2][c][0] = new_cost
						set2.add((r + 2, c, 0))
				if issafe(r, c - 1, r + 1, c - 1, graph):
					if cost_graph[r][c - 1][2] == -1 or cost_graph[r][c - 1][2] > new_cost:
						cost_graph[r][c - 1][2] = new_cost
						set2.add((r, c - 1, 2))
				if issafe(r - 1, c, r - 1, c, graph):
					if cost_graph[r - 1][c][0] == -1 or cost_graph[r - 1][c][0] > new_cost:
						cost_graph[r - 1][c][0] = new_cost
						set2.add((r - 1, c, 0))
		set1 = set2
	for _ in range(n):
		for __ in range(m):
			print(cost_graph[_][__][0], end=' ')
		print()


from math import inf
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	(r, c) = map(int, input().split())
	grid = [[False] * (m + 2) for __ in range(n + 2)]
	for i in range(n):
		s = input()
		for (j, x) in enumerate(s):
			grid[i][j] = x == '1'
	solution = [[[inf, inf, inf] for ___ in range(m)] for __ in range(n)]
	r -= 1
	c -= 1
	solution[r][c][0] = 0
	touched_set = set()
	touched_set.add((r, c, 0))
	while len(touched_set):
		new_touched_set = set()
		while len(touched_set):
			(r, c, o) = touched_set.pop()
			new_sol = 1 + solution[r][c][o]
			if o == 0:
				if grid[r][c + 1] and grid[r][c + 2] and (solution[r][c + 1][1] > new_sol):
					solution[r][c + 1][1] = new_sol
					new_touched_set.add((r, c + 1, 1))
				if grid[r + 1][c] and grid[r + 2][c] and (solution[r + 1][c][2] > new_sol):
					solution[r + 1][c][2] = new_sol
					new_touched_set.add((r + 1, c, 2))
				if grid[r][c - 2] and grid[r][c - 1] and (solution[r][c - 2][1] > new_sol):
					solution[r][c - 2][1] = new_sol
					new_touched_set.add((r, c - 2, 1))
				if grid[r - 2][c] and grid[r - 1][c] and (solution[r - 2][c][2] > new_sol):
					solution[r - 2][c][2] = new_sol
					new_touched_set.add((r - 2, c, 2))
			elif o == 1:
				if grid[r][c + 2] and solution[r][c + 2][0] > new_sol:
					solution[r][c + 2][0] = new_sol
					new_touched_set.add((r, c + 2, 0))
				if grid[r + 1][c] and grid[r + 1][c + 1] and (solution[r + 1][c][1] > new_sol):
					solution[r + 1][c][1] = new_sol
					new_touched_set.add((r + 1, c, 1))
				if grid[r][c - 1] and solution[r][c - 1][0] > new_sol:
					solution[r][c - 1][0] = new_sol
					new_touched_set.add((r, c - 1, 0))
				if grid[r - 1][c] and grid[r - 1][c + 1] and (solution[r - 1][c][1] > new_sol):
					solution[r - 1][c][1] = new_sol
					new_touched_set.add((r - 1, c, 1))
			else:
				if grid[r][c + 1] and grid[r + 1][c + 1] and (solution[r][c + 1][2] > new_sol):
					solution[r][c + 1][2] = new_sol
					new_touched_set.add((r, c + 1, 2))
				if grid[r + 2][c] and solution[r + 2][c][0] > new_sol:
					solution[r + 2][c][0] = new_sol
					new_touched_set.add((r + 2, c, 0))
				if grid[r][c - 1] and grid[r + 1][c - 1] and (solution[r][c - 1][2] > new_sol):
					solution[r][c - 1][2] = new_sol
					new_touched_set.add((r, c - 1, 2))
				if grid[r - 1][c] and solution[r - 1][c][0] > new_sol:
					solution[r - 1][c][0] = new_sol
					new_touched_set.add((r - 1, c, 0))
		touched_set = new_touched_set
	for i in range(n):
		for j in range(m):
			print(solution[i][j][0] if solution[i][j][0] != inf else -1, end=' ')
		print()


from math import inf
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	(r, c) = map(int, input().split())
	grid = [[False] * (m + 2) for __ in range(n + 2)]
	for i in range(n):
		s = input()
		for (j, x) in enumerate(s):
			grid[i][j] = x == '1'
	solution = [[[inf, inf, inf] for ___ in range(m)] for __ in range(n)]
	r -= 1
	c -= 1
	solution[r][c][0] = 0
	A = []
	B = []
	C = []
	A.append(r)
	B.append(c)
	C.append(0)
	while len(A):
		r = A.pop(0)
		c = B.pop(0)
		o = C.pop(0)
		new_sol = 1 + solution[r][c][o]
		if o == 0:
			if grid[r][c + 1] and grid[r][c + 2] and (solution[r][c + 1][1] > new_sol):
				solution[r][c + 1][1] = new_sol
				A.append(r)
				B.append(c + 1)
				C.append(1)
			if grid[r + 1][c] and grid[r + 2][c] and (solution[r + 1][c][2] > new_sol):
				solution[r + 1][c][2] = new_sol
				A.append(r + 1)
				B.append(c)
				C.append(2)
			if grid[r][c - 2] and grid[r][c - 1] and (solution[r][c - 2][1] > new_sol):
				solution[r][c - 2][1] = new_sol
				A.append(r)
				B.append(c - 2)
				C.append(1)
			if grid[r - 2][c] and grid[r - 1][c] and (solution[r - 2][c][2] > new_sol):
				solution[r - 2][c][2] = new_sol
				A.append(r - 2)
				B.append(c)
				C.append(2)
		elif o == 1:
			if grid[r][c + 2] and solution[r][c + 2][0] > new_sol:
				solution[r][c + 2][0] = new_sol
				A.append(r)
				B.append(c + 2)
				C.append(0)
			if grid[r + 1][c] and grid[r + 1][c + 1] and (solution[r + 1][c][1] > new_sol):
				solution[r + 1][c][1] = new_sol
				A.append(r + 1)
				B.append(c)
				C.append(1)
			if grid[r][c - 1] and solution[r][c - 1][0] > new_sol:
				solution[r][c - 1][0] = new_sol
				A.append(r)
				B.append(c - 1)
				C.append(0)
			if grid[r - 1][c] and grid[r - 1][c + 1] and (solution[r - 1][c][1] > new_sol):
				solution[r - 1][c][1] = new_sol
				A.append(r - 1)
				B.append(c)
				C.append(1)
		else:
			if grid[r][c + 1] and grid[r + 1][c + 1] and (solution[r][c + 1][2] > new_sol):
				solution[r][c + 1][2] = new_sol
				A.append(r)
				B.append(c + 1)
				C.append(2)
			if grid[r + 2][c] and solution[r + 2][c][0] > new_sol:
				solution[r + 2][c][0] = new_sol
				A.append(r + 2)
				B.append(c)
				C.append(0)
			if grid[r][c - 1] and grid[r + 1][c - 1] and (solution[r][c - 1][2] > new_sol):
				solution[r][c - 1][2] = new_sol
				A.append(r)
				B.append(c - 1)
				C.append(2)
			if grid[r - 1][c] and solution[r - 1][c][0] > new_sol:
				solution[r - 1][c][0] = new_sol
				A.append(r - 1)
				B.append(c)
				C.append(0)
	for i in range(n):
		for j in range(m):
			print(solution[i][j][0] if solution[i][j][0] != inf else -1, end=' ')
		print()


from math import inf
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(r, c) = map(int, input().split())
	a = [[0] * (m + 2) for _ in range(n + 2)]
	for i in range(n):
		s = input()
		for (j, x) in enumerate(s):
			a[i][j] = x
	r -= 1
	c -= 1
	ans = [[[inf, inf, inf] for i in range(m)] for j in range(n)]
	ans[r][c][0] = 0
	touched = set()
	touched.add((r, c, 0))
	while len(touched):
		visited = set()
		while len(touched):
			(r, c, o) = touched.pop()
			count = 1 + ans[r][c][o]
			if o == 0:
				if a[r][c + 1] == '1' and a[r][c + 2] == '1' and (ans[r][c + 1][1] > count):
					ans[r][c + 1][1] = count
					visited.add((r, c + 1, 1))
				if a[r][c - 2] == '1' and a[r][c - 1] == '1' and (ans[r][c - 2][1] > count):
					ans[r][c - 2][1] = count
					visited.add((r, c - 2, 1))
				if a[r + 1][c] == '1' and a[r + 2][c] == '1' and (ans[r + 1][c][2] > count):
					ans[r + 1][c][2] = count
					visited.add((r + 1, c, 2))
				if a[r - 1][c] == '1' and a[r - 2][c] == '1' and (ans[r - 2][c][2] > count):
					ans[r - 2][c][2] = count
					visited.add((r - 2, c, 2))
			elif o == 1:
				if a[r][c + 2] == '1' and ans[r][c + 2][0] > count:
					ans[r][c + 2][0] = count
					visited.add((r, c + 2, 0))
				if a[r][c - 1] == '1' and ans[r][c - 1][0] > count:
					ans[r][c - 1][0] = count
					visited.add((r, c - 1, 0))
				if a[r + 1][c] == '1' and a[r + 1][c + 1] == '1' and (ans[r + 1][c][1] > count):
					ans[r + 1][c][1] = count
					visited.add((r + 1, c, 1))
				if a[r - 1][c] == '1' and a[r - 1][c + 1] == '1' and (ans[r - 1][c][1] > count):
					ans[r - 1][c][1] = count
					visited.add((r - 1, c, 1))
			else:
				if a[r][c + 1] == '1' and a[r + 1][c + 1] == '1' and (ans[r][c + 1][2] > count):
					ans[r][c + 1][2] = count
					visited.add((r, c + 1, 2))
				if a[r][c - 1] == '1' and a[r + 1][c - 1] == '1' and (ans[r][c - 1][2] > count):
					ans[r][c - 1][2] = count
					visited.add((r, c - 1, 2))
				if a[r + 2][c] == '1' and ans[r + 2][c][0] > count:
					ans[r + 2][c][0] = count
					visited.add((r + 2, c, 0))
				if a[r - 1][c] == '1' and ans[r - 1][c][0] > count:
					ans[r - 1][c][0] = count
					visited.add((r - 1, c, 0))
		touched = visited
	for i in range(n):
		for j in range(m):
			print(ans[i][j][0] if ans[i][j][0] != inf else -1, end=' ')
		print()