Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

In Chefland, there is a monthly robots competition. In the competition, a grid table of N rows and M columns will be used to place robots. A cell at row i and column j in the table is called cell (i, j). To join this competition, each player will bring two robots to compete and each robot will be placed at a cell in the grid table. Both robots will move at the same time from one cell to another until they meet at the same cell in the table. Of course they can not move outside the table. Each robot has a movable range. If a robot has movable range K, then in a single move, it can move from cell (x, y) to cell (i, j) provided (|i-x| + |j-y| ≤ K). However, there are some cells in the table that the robots can not stand at, and because of that, they can not move to these cells. The two robots with the minimum number of moves to be at the same cell will win the competition.

Chef plans to join the competition and has two robots with the movable range K1 and K2, respectively. Chef does not know which cells in the table will be used to placed his 2 robots, but he knows that there are 2 cells (1, 1) and (1, M) that robots always can stand at. Therefore, he assumes that the first robot is at cell (1, 1) and the other is at cell (1, M). Chef wants you to help him to find the minimum number of moves that his two robots needed to be at the same cell and promises to give you a gift if he wins the competition. 

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains 4 space-separated integers N M K1 K2 denoting the number of rows and columns in the table and the movable ranges of the first and second robot of Chef.
The next N lines, each line contains M space-separated numbers either 0 or 1 denoting whether the robots can move to this cell or not (0 means robots can move to this cell, 1 otherwise). It makes sure that values in cell (1, 1) and cell (1, M) are 0.

------ Output ------ 

For each test case, output a single line containing the minimum number of moves that Chef’s 2 robots needed to be at the same cell. If they can not be at the same cell, print -1.

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ N, M ≤ 100
0 ≤ K1, K2 ≤ 10

------  Subtasks  ------ 

Subtask #1 : (25 points) 

K1 = K2 = 1 

Subtask # 2 : (75 points) 

Original Constraints

----- Sample Input 1 ------ 
2

4 4 1 1

0 1 1 0

0 1 1 0

0 1 1 0

0 0 0 0

4 4 1 1

0 1 1 0

0 1 1 0

0 1 1 0

1 0 0 1
----- Sample Output 1 ------ 
5

-1
----- explanation 1 ------ 
Example case 1. Robot 1 can move (1, 1) -> (2, 1) -> (3, 1) -> (4, 1) -> (4, 2) -> (4, 3), and robot 2 can move (1, 4) -> (2, 4) -> (3, 4) -> (4, 4) -> (4, 3) -> (4, 3), they meet at cell (4, 3) after 5 moves.
Example case 2. Because the movable range of both robots is 1, robot 1 can not move from (3, 1) to (4, 2), and robot 2 can not move from (3, 4) to (4, 3. Hence, they can not meet each other.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Implementation


Solutions:
from collections import deque
for _ in range(int(input())):
	(n, m, k1, k2) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	robo1 = [[-1] * m for i in range(n)]
	robo2 = [[-1] * m for i in range(n)]
	robo1[0][0] = 0
	robo2[0][m - 1] = 0
	Q = deque([(0, 0)])
	while Q:
		(i, j) = Q.popleft()
		for x in range(max(i - k1, 0), min(i + k1 + 1, n)):
			t = abs(i - x)
			for y in range(max(0, j - k1 + t), min(j + k1 - t + 1, m)):
				if arr[x][y] == 0 and robo1[x][y] == -1:
					robo1[x][y] = robo1[i][j] + 1
					Q.append((x, y))
	Q = deque([(0, m - 1)])
	while Q:
		(i, j) = Q.popleft()
		for x in range(max(i - k2, 0), min(i + k2 + 1, n)):
			t = abs(i - x)
			for y in range(max(0, j - k2 + t), min(j + k2 - t + 1, m)):
				if arr[x][y] == 0 and robo2[x][y] == -1:
					robo2[x][y] = robo2[i][j] + 1
					Q.append((x, y))
	ans = float('inf')
	for i in range(n):
		for j in range(m):
			if robo1[i][j] != -1 and robo2[i][j] != -1:
				ans = min(ans, max(robo1[i][j], robo2[i][j]))
	print(-1 if ans == float('inf') else ans)


(a, b) = (0, 1)
for t in range(int(input())):
	k = [None] * 2
	(n, m, k[a], k[b]) = [int(i) for i in input().split()]
	visited = [{(0, 0)}, {(0, m - 1)}]
	minmoves = [{(0, 0): 0}, {(0, m - 1): 0}]
	blocked = set()
	for i in range(n):
		row = [int(i) for i in input().split()]
		for j in range(m):
			if row[j] == 1:
				blocked.add((i, j))
	movetemplate = [set(), set()]
	for r in range(2):
		for x in range(-1 * k[r], k[r] + 1):
			for y in range(-1 * k[r] + abs(x), k[r] - abs(x) + 1):
				movetemplate[r].add((x, y))
		movetemplate[r].remove((0, 0))
	now = [{(0, 0)}, {(0, m - 1)}]
	c = 1

	def applymoves(r):
		nxt = set()
		for p0 in now[r]:
			for move in movetemplate[r]:
				p1 = (p0[0] + move[0], p0[1] + move[1])
				if p1[0] >= 0 and p1[0] < n and (p1[1] >= 0) and (p1[1] < m):
					if not p1 in visited[r] and (not p1 in blocked):
						visited[r].add(p1)
						minmoves[r][p1] = c
						nxt.add(p1)
		return nxt
	r = 0
	while True:
		now[r] = applymoves(r)
		if not (now[a] or now[b]) or visited[a] & visited[b]:
			break
		c += 1 if r == 1 else 0
		r = (r + 1) % 2
	if visited[a] & visited[b]:
		p = (visited[a] & visited[b]).pop()
		print(max(minmoves[a][p], minmoves[b][p]))
	else:
		print(-1)


def calc(grid, n, m, x1, y1, k1, x2, y2, k2):
	res1 = [[-1 for j in range(m)] for i in range(n)]
	res2 = [[-1 for j in range(m)] for i in range(n)]
	res1[x1][y1] = 0
	res2[x2][y2] = 0
	q1 = []
	q2 = []
	directions = [[1, 1], [-1, -1], [1, -1], [-1, 1]]
	q1.append([x1, y1])
	q2.append([x2, y2])
	while len(q1) > 0 or len(q2) > 0:
		if len(q1) > 0:
			nq1 = []
			for pos in q1:
				for jump in range(1, k1 + 1):
					for hor in range(0, jump + 1):
						for d in directions:
							newPos = [pos[0] + hor * d[0], pos[1] + (jump - hor) * d[1]]
							if newPos[0] >= 0 and newPos[0] < n and (newPos[1] >= 0) and (newPos[1] < m):
								if grid[newPos[0]][newPos[1]] == 0:
									if res1[newPos[0]][newPos[1]] == -1:
										res1[newPos[0]][newPos[1]] = res1[pos[0]][pos[1]] + 1
										nq1.append(newPos)
									if res2[newPos[0]][newPos[1]] != -1:
										print(max(res1[newPos[0]][newPos[1]], res2[newPos[0]][newPos[1]]))
										return
			q1 = nq1
		if len(q2) > 0:
			nq2 = []
			for pos in q2:
				for jump in range(1, k2 + 1):
					for hor in range(0, jump + 1):
						for d in directions:
							newPos = [pos[0] + hor * d[0], pos[1] + (jump - hor) * d[1]]
							if newPos[0] >= 0 and newPos[0] < n and (newPos[1] >= 0) and (newPos[1] < m):
								if grid[newPos[0]][newPos[1]] == 0:
									if res2[newPos[0]][newPos[1]] == -1:
										res2[newPos[0]][newPos[1]] = res2[pos[0]][pos[1]] + 1
										nq2.append(newPos)
									if res1[newPos[0]][newPos[1]] != -1:
										print(max(res1[newPos[0]][newPos[1]], res2[newPos[0]][newPos[1]]))
										return
			q2 = nq2
	print(-1)
T = int(input())
for t in range(T):
	p = [int(x) for x in input().split(' ')]
	n = p[0]
	m = p[1]
	k1 = p[2]
	k2 = p[3]
	grid = [[int(x) for x in input().split(' ')] for i in range(n)]
	calc(grid, n, m, 0, 0, k1, 0, m - 1, k2)


def ans(l, n, m, k1):
	x = {(0, 0): 0}
	l1 = [(0, 0)]
	l[0][0] = 1
	while len(l1) > 0:
		(i, j) = l1[0]
		l1 = l1[1:]
		i1 = max(0, i - k1)
		while i1 <= min(i + k1, n - 1):
			ip = abs(i - i1)
			j1 = max(0, j - k1 + ip)
			while j1 <= min(j + k1 - ip, m - 1):
				if l[i1][j1] == 0:
					if abs(i1 - i) + abs(j1 - j) <= k1:
						x[i1, j1] = x[i, j] + 1
						l1 += [(i1, j1)]
						l[i1][j1] = 1
					if (i1, j1) == (0, m - 1):
						j1 = 10 ** 9
						i1 = 10 ** 9
						l1 = []
				j1 += 1
			i1 += 1
	return x

def ans1(l, n, m, k1):
	x = {(0, m - 1): 0}
	l1 = [(0, m - 1)]
	l[0][m - 1] = 1
	while len(l1) > 0:
		(i, j) = l1[0]
		l1 = l1[1:]
		i1 = max(0, i - k1)
		while i1 <= min(i + k1, n - 1):
			ip = abs(i - i1)
			j1 = max(0, j - k1 + ip)
			while j1 <= min(j + k1 - ip, m - 1):
				if l[i1][j1] == 0:
					if abs(i1 - i) + abs(j1 - j) <= k1:
						x[i1, j1] = x[i, j] + 1
						l1 += [(i1, j1)]
						l[i1][j1] = 1
					if (i1, j1) == (0, 0):
						j1 = 10 ** 9
						i1 = 10 ** 9
						l1 = []
				j1 += 1
			i1 += 1
	return x

def unshared_copy(inList):
	if isinstance(inList, list):
		return list(map(unshared_copy, inList))
	return inList

def a(l, m, n, k1, k2):
	ll = unshared_copy(l)
	x1 = ans(ll, m, n, k1)
	x2 = ans1(l, m, n, k2)
	x = 10 ** 9
	f = 1
	for k in x1:
		if k in x2:
			x = min(x, max(x1[k], x2[k]))
			f = 0
	if f == 1:
		return -1
	else:
		return x
t = int(input())
while t != 0:
	t -= 1
	(n, m, k1, k2) = map(int, input().split())
	l = []
	i = 0
	while i < n:
		l += [list(map(int, input().split()))]
		i += 1
	print(a(l, n, m, k1, k2))


T = int(input())
while T > 0:
	T -= 1
	(N, M, K1, K2) = [int(x) for x in input().split()]
	c = N
	mat = []
	while c > 0:
		c -= 1
		r = [int(x) for x in input().split()]
		mat.append(r)
	pmoves1 = {(0, 0): 0}
	pmoves2 = {(0, M - 1): 0}
	uncover1 = set([(0, 0)])
	uncover2 = set([(0, M - 1)])
	mcnt1 = mcnt2 = 1
	Complete1 = Complete2 = False
	while not Complete1 or not Complete2:
		tmp = set()
		while uncover1:
			e = uncover1.pop()
			for i in range(K1 + 1):
				for j in range(K1 + 1):
					if i + j <= K1:
						if e[0] + i < N and e[1] + j < M and ((e[0] + i, e[1] + j) not in pmoves1) and (mat[e[0] + i][e[1] + j] == 0):
							tmp.add((e[0] + i, e[1] + j))
							pmoves1[e[0] + i, e[1] + j] = mcnt1
						if e[0] - i >= 0 and e[1] + j < M and ((e[0] - i, e[1] + j) not in pmoves1) and (mat[e[0] - i][e[1] + j] == 0):
							tmp.add((e[0] - i, e[1] + j))
							pmoves1[e[0] - i, e[1] + j] = mcnt1
						if e[0] + i < N and e[1] - j >= 0 and ((e[0] + i, e[1] - j) not in pmoves1) and (mat[e[0] + i][e[1] - j] == 0):
							tmp.add((e[0] + i, e[1] - j))
							pmoves1[e[0] + i, e[1] - j] = mcnt1
						if e[0] - i >= 0 and e[1] - j >= 0 and ((e[0] - i, e[1] - j) not in pmoves1) and (mat[e[0] - i][e[1] - j] == 0):
							tmp.add((e[0] - i, e[1] - j))
							pmoves1[e[0] - i, e[1] - j] = mcnt1
		if tmp:
			uncover1 = tmp.copy()
			mcnt1 += 1
		else:
			Complete1 = True
		tmp = set()
		while uncover2:
			e = uncover2.pop()
			for i in range(K2 + 1):
				for j in range(K2 + 1):
					if i + j <= K2:
						if e[0] + i < N and e[1] + j < M and ((e[0] + i, e[1] + j) not in pmoves2) and (mat[e[0] + i][e[1] + j] == 0):
							tmp.add((e[0] + i, e[1] + j))
							pmoves2[e[0] + i, e[1] + j] = mcnt2
						if e[0] - i >= 0 and e[1] + j < M and ((e[0] - i, e[1] + j) not in pmoves2) and (mat[e[0] - i][e[1] + j] == 0):
							tmp.add((e[0] - i, e[1] + j))
							pmoves2[e[0] - i, e[1] + j] = mcnt2
						if e[0] + i < N and e[1] - j >= 0 and ((e[0] + i, e[1] - j) not in pmoves2) and (mat[e[0] + i][e[1] - j] == 0):
							tmp.add((e[0] + i, e[1] - j))
							pmoves2[e[0] + i, e[1] - j] = mcnt2
						if e[0] - i >= 0 and e[1] - j >= 0 and ((e[0] - i, e[1] - j) not in pmoves2) and (mat[e[0] - i][e[1] - j] == 0):
							tmp.add((e[0] - i, e[1] - j))
							pmoves2[e[0] - i, e[1] - j] = mcnt2
		if tmp:
			uncover2 = tmp.copy()
			mcnt2 += 1
		else:
			Complete2 = True
		if set(pmoves1.keys()) & set(pmoves2.keys()):
			break
	meet_points = set(pmoves1.keys()) & set(pmoves2.keys())
	moves = []
	for point in meet_points:
		moves.append(max(pmoves1[point], pmoves2[point]))
	if moves:
		print(min(moves))
	else:
		print(-1)