Given a N*M grid of characters 'O', 'X', and 'Y'. Find the minimum Manhattan distance between a X and a Y.
Manhattan Distance :
| row_index_x - row_index_y | + | column_index_x - column_index_y |
Example 1:
Input:
N = 4, M = 4
grid  = {{X, O, O, O}
         {O, Y, O, Y}
         {X, X, O, O}
         {O, Y, O, O}}
Output:
1
Explanation:
{{X, O, O, O}
{O, Y, O, Y}
{X, X, O, O}
{O, Y, O, O}}
The shortest X-Y distance in the grid is 1.
One possible such X and Y are marked in bold
in the above grid.
Example 2:
Input:
N = 3, M = 3
grid = {{X, X, O}
        {O, O, Y}
        {Y, O, O}}
Output :
2
Explanation:
{{X, X, O}
 {O, O, Y}
 {Y, O, O}}
The shortest X-Y distance in the grid is 2.
One possible such X and Y are marked in bold
in the above grid.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function shortestXYDist() which takes two integers N, and M and an 2D list of size N*M as input and returns the shortest Manhattan Distance between a X and a Y.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ N*M ≤ 10^{5}^{ }
There exists at least one 'X' and at least one 'Y' in the grid.

Difficulty: MEDIUM
Tags: Dynamic programming

Graph traversal
Skill types: Dynamic programming
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)

Starter code:
#User function Template for python3



class Solution:

    def shortestXYDist(self, grid, N, M):

        # code here 

Solutions:
from copy import deepcopy
from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		row = [0 for i in range(M)]
		visited = [deepcopy(row) for i in range(N)]
		(self.N, self.M) = (N, M)
		queue = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					queue.append((i, j, 0))
		return self.bfs(visited, queue, grid)

	def bfs(self, visited, queue, grid):
		min_dist = float('inf')
		while queue:
			(x, y, dist) = queue.popleft()
			if x < 0 or x >= self.N or y < 0 or (y >= self.M) or visited[x][y]:
				continue
			visited[x][y] = 1
			if grid[x][y] == 'Y':
				min_dist = min(dist, min_dist)
			queue.append((x + 1, y, dist + 1))
			queue.append((x, y + 1, dist + 1))
			queue.append((x - 1, y, dist + 1))
			queue.append((x, y - 1, dist + 1))
		return min_dist


class Solution:

	def shortestXYDist(self, G, N, M):
		i = 10 ** 8
		dp = [[i] * (M + 2) for _ in range(N + 2)]
		for r in range(1, N + 1):
			for c in range(1, M + 1):
				dp[r][c] = 0 if G[r - 1][c - 1] == 'X' else min(dp[r - 1][c], dp[r][c - 1]) + 1
		for r in range(N, 0, -1):
			for c in range(M, 0, -1):
				dp[r][c] = min(dp[r][c], 1 + dp[r + 1][c], 1 + dp[r][c + 1])
		ans = min((dp[r][c] for r in range(1, N + 1) for c in range(1, M + 1) if G[r - 1][c - 1] == 'Y'))
		return ans


class Solution:

	def shortestXYDist(self, grid, n, m):
		x_positions = []
		y_positions = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					x_positions.append((i, j))
				elif grid[i][j] == 'Y':
					y_positions.append((i, j))
		min_distance = float('inf')
		for x_pos in x_positions:
			for y_pos in y_positions:
				distance = abs(x_pos[0] - y_pos[0]) + abs(x_pos[1] - y_pos[1])
				if distance < min_distance:
					min_distance = distance
					if min_distance == 1:
						return 1
		return min_distance


class Solution:

	def shortestXYDist(self, grid, N, M):
		from collections import deque
		q = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append((i, j, 0))
		seen = set()
		while q:
			nq = deque()
			while q:
				(x, y, cnt) = q.popleft()
				if (x, y) in seen:
					continue
				seen.add((x, y))
				if grid[x][y] == 'Y':
					return cnt
				cnt += 1
				for (nx, ny) in [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]]:
					if 0 <= nx < N and 0 <= ny < M:
						nq.append((nx, ny, cnt))
			q = nq


from queue import Queue

class Solution:

	def shortestXYDist(self, grid, N, M):
		adjs = [1, 0, -1, 0, 1]
		q = Queue()
		dists = [[None for _ in range(M)] for _ in range(N)]
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					dists[i][j] = (0, grid[i][j])
					q.put((i, j))
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'Y':
					dists[i][j] = (0, grid[i][j])
					q.put((i, j))
		while q:
			(i, j) = q.get()
			(d, m) = dists[i][j]
			for k in range(4):
				(adj_i, adj_j) = (i + adjs[k], j + adjs[k + 1])
				if adj_i < 0 or adj_i == N or adj_j < 0 or (adj_j == M):
					continue
				if dists[adj_i][adj_j] is None:
					dists[adj_i][adj_j] = (d + 1, m)
					q.put((adj_i, adj_j))
					continue
				elif dists[adj_i][adj_j][1] != m:
					return d + dists[adj_i][adj_j][0] + 1
		return -1


class Solution:

	def shortestXYDist(self, grid, N, M):
		lst_x = []
		lst_y = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					lst_x.append([i, j])
				elif grid[i][j] == 'Y':
					lst_y.append([i, j])
		manhattan = N * M
		for i in range(len(lst_x)):
			for j in range(len(lst_y)):
				manhattan = min(manhattan, abs(lst_x[i][0] - lst_y[j][0]) + abs(lst_x[i][1] - lst_y[j][1]))
				if manhattan == 1:
					break
		return manhattan


class Solution:

	def partial(x, y, A):
		mincost = 200001
		for opp in A:
			mincost = min(mincost, abs(opp[0] - x) + abs(opp[1] - y))
		return mincost

	def shortestXYDist(self, grid, N, M):
		(Xs, Ys, mincost) = ([], [], 200001)
		for i in range(N):
			if mincost == 1:
				return 1
			for j in range(M):
				if grid[i][j] == 'X':
					Xs.append([i, j])
					mincost = min(mincost, Solution.partial(i, j, Ys))
				if grid[i][j] == 'Y':
					Ys.append([i, j])
					mincost = min(mincost, Solution.partial(i, j, Xs))
		return mincost


from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		vis = [[-1] * M for i in range(N)]
		q = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append(([i, j], 0))
					vis[i][j] = 1
		while q:
			(coord, step) = q.popleft()
			r = coord[0]
			c = coord[1]
			if grid[r][c] == 'Y':
				return step
			dr = [-1, 1, 0, 0]
			dc = [0, 0, -1, 1]
			for i in range(4):
				nr = r + dr[i]
				nc = c + dc[i]
				if nr >= 0 and nr < N and (nc >= 0) and (nc < M) and (vis[nr][nc] != 1):
					q.append(([nr, nc], step + 1))
					vis[nr][nc] = 1
		return -1


from collections import deque

class Solution:

	def shortestXYDist(self, a, n, m):
		q = deque()
		vis = [[0] * m for i in range(n)]
		row = [0, -1, 0, 1]
		col = [-1, 0, 1, 0]
		for i in range(n):
			for j in range(m):
				if a[i][j] == 'X':
					q.append((i, j))
					vis[i][j] = 1
		s = 0
		while q:
			qn = len(q)
			while qn:
				node = q.popleft()
				(r, c) = (node[0], node[1])
				if a[r][c] == 'Y':
					return s
				for k in range(4):
					ro = r + row[k]
					co = c + col[k]
					if ro >= 0 and co >= 0 and (ro < n) and (co < m) and (vis[ro][co] == 0):
						q.append((ro, co))
						vis[ro][co] = 1
				qn -= 1
			s += 1
		return -1


class Solution:

	def shortestXYDist(self, grid, N, M):
		q = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					grid[i][j] = 0
					q.append((i, j))
		while q:
			(i, j) = q.pop(0)
			for (a, b) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= a < N and 0 <= b < M:
					if grid[a][b] == 'Y':
						return grid[i][j] + 1
					if grid[a][b] == 'O':
						grid[a][b] = grid[i][j] + 1
						q.append((a, b))


class Solution:

	def shortestXYDist(self, grid, N, M):
		dist = [[float('inf')] * M for _ in range(N)]
		for y in range(N):
			for x in range(M):
				if grid[y][x] == 'X':
					dist[y][x] = 0
				else:
					if y > 0:
						dist[y][x] = min(dist[y][x], dist[y - 1][x] + 1)
					if x > 0:
						dist[y][x] = min(dist[y][x], dist[y][x - 1] + 1)
		for y in range(N - 1, -1, -1):
			for x in range(M - 1, -1, -1):
				if grid[y][x] == 'X':
					dist[y][x] = 0
				else:
					if y < N - 1:
						dist[y][x] = min(dist[y][x], dist[y + 1][x] + 1)
					if x < M - 1:
						dist[y][x] = min(dist[y][x], dist[y][x + 1] + 1)
		ans = 1000000000.0
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'Y':
					ans = min(ans, dist[i][j])
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		x_vals = {}
		y_vals = {}
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					x_vals[i, j] = 'vdv'
				if grid[i][j] == 'Y':
					y_vals[i, j] = 'adv'
		mins = 845648584
		for i in x_vals:
			for j in y_vals:
				if mins == 1:
					return 1
				if abs(i[0] - j[0]) + abs(i[1] - j[1]) < mins:
					mins = abs(i[0] - j[0]) + abs(i[1] - j[1])
		return mins


class Solution:

	def shortestXYDist(self, grid, N, M):
		location_dict = self.find_XY_location(grid, N, M)
		least_distance = self.find_XY_dist_list(location_dict)
		return least_distance

	def find_XY_location(self, grid, N, M):
		location_dict = {'X': [], 'Y': [], 'X_len': 0, 'Y_len': 0}
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					location_dict['X'].append([i, j])
					location_dict['X_len'] += 1
				elif grid[i][j] == 'Y':
					location_dict['Y'].append([i, j])
					location_dict['Y_len'] += 1
		return location_dict

	def find_XY_dist_list(self, location_dict):
		lowest_distance = abs(location_dict['X'][0][0] - location_dict['Y'][0][0]) + abs(location_dict['X'][0][1] - location_dict['Y'][0][1])
		for i in range(location_dict['X_len']):
			if lowest_distance == 1:
				break
			for j in range(location_dict['Y_len']):
				temp_distance = abs(location_dict['X'][i][0] - location_dict['Y'][j][0]) + abs(location_dict['X'][i][1] - location_dict['Y'][j][1])
				if temp_distance < lowest_distance:
					lowest_distance = temp_distance
		return lowest_distance


from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):

		def isvalid(x, y):
			if x < 0 or y < 0 or x >= N or (y >= M) or (vis[x][y] == True):
				return False
			return True
		q = deque()
		vis = [[False] * M for i in range(N)]
		for i in range(0, N):
			for j in range(0, M):
				if grid[i][j] == 'X':
					q.append((i, j, 0))
					vis[i][j] = True
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		while q:
			(x, y, dist) = q.popleft()
			if grid[x][y] == 'Y':
				return dist
			for d in directions:
				newx = x + d[0]
				newy = y + d[1]
				if isvalid(newx, newy):
					q.append((newx, newy, dist + 1))
					vis[newx][newy] = True


class Solution:

	def shortestXYDist(self, grid, N, M):
		w = 10 ** 6
		dp = [[0 for i in range(M)] for j in range(N)]
		ans = float('inf')
		for i in range(N):
			for j in range(M):
				if grid[i][j] != 'X':
					dp[i][j] = w
		for i in range(N):
			for j in range(M):
				mindistance = 10 ** 6
				if grid[i][j] != 'X':
					if i + 1 < N:
						mindistance = min(mindistance, dp[i + 1][j])
					if i - 1 >= 0:
						mindistance = min(mindistance, dp[i - 1][j])
					if j + 1 < M:
						mindistance = min(mindistance, dp[i][j + 1])
					if j - 1 >= 0:
						mindistance = min(mindistance, dp[i][j - 1])
				if mindistance != 10 ** 6:
					dp[i][j] = mindistance + 1
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				mindistance = 10 ** 6
				if grid[i][j] != 'X':
					if i + 1 < N:
						mindistance = min(mindistance, dp[i + 1][j])
					if i - 1 >= 0:
						mindistance = min(mindistance, dp[i - 1][j])
					if j + 1 < M:
						mindistance = min(mindistance, dp[i][j + 1])
					if j - 1 >= 0:
						mindistance = min(mindistance, dp[i][j - 1])
				if mindistance != 10 ** 6:
					dp[i][j] = min(dp[i][j], mindistance + 1)
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'Y':
					ans = min(ans, dp[i][j])
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		x = []
		y = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					x.append([i, j])
				elif grid[i][j] == 'Y':
					y.append([i, j])
		s = N * M
		for i in range(len(x)):
			for j in range(len(y)):
				k = abs(x[i][0] - y[j][0]) + abs(x[i][1] - y[j][1])
				s = min(s, k)
				if s == 1:
					break
		return s


from collections import deque
from itertools import product

class Solution:

	def shortestXYDist(self, grid, M, N):
		(Q, visited) = (deque(), set())
		DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		for (i, j) in product(range(M), range(N)):
			if grid[i][j] == 'X':
				Q.append(((i, j), 0))
				visited.add((i, j))
		while Q:
			for _ in range(len(Q)):
				((row, col), dist) = Q.popleft()
				if grid[row][col] == 'Y':
					return dist
				for (i, j) in DIR:
					(new_r, new_c) = (row + i, col + j)
					if new_r < 0 or new_c < 0 or new_r >= M or (new_c >= N) or ((new_r, new_c) in visited):
						continue
					Q.append(((new_r, new_c), dist + 1))
					visited.add((new_r, new_c))
		return -1


class Solution:

	def shortestXYDist(self, grid, N, M):
		q = []
		visited = [[0 for i in range(M)] for j in range(N)]
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append([[i, j], 0])
					visited[i][j] = 1
		rows = [1, 0, 0, -1]
		cols = [0, 1, -1, 0]
		ans = 0
		while q:
			front = q.pop(0)
			i = front[0][0]
			j = front[0][1]
			dis = front[1]
			if grid[i][j] == 'Y':
				ans = dis
				break
			for k in range(4):
				nrow = i + rows[k]
				ncol = j + cols[k]
				if nrow >= 0 and nrow < N and (ncol >= 0) and (ncol < M) and (visited[nrow][ncol] == 0):
					q.append([[nrow, ncol], dis + 1])
					visited[nrow][ncol] = 1
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		d = [[float('inf')] * M for i in range(N)]
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					d[i][j] = 0
				else:
					if j > 0:
						d[i][j] = min(d[i][j], d[i][j - 1] + 1)
					if i > 0:
						d[i][j] = min(d[i][j], d[i - 1][j] + 1)
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if grid[i][j] == 'X':
					d[i][j] = 0
				else:
					if j < M - 1:
						d[i][j] = min(d[i][j], d[i][j + 1] + 1)
					if i < N - 1:
						d[i][j] = min(d[i][j], d[i + 1][j] + 1)
		ans = 1000000000.0
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'Y':
					ans = min(ans, d[i][j])
		return ans


from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		q = deque()
		visited = []
		for i in range(N):
			l = []
			for j in range(M):
				l.append(0)
			visited.append(l)
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append([i, j, 0])
					visited[i][j] = 1
		ans = 1000000000.0
		while len(q) != 0:
			(x_cor, y_cor, steps) = q.popleft()
			drow = [-1, 0, 1, 0]
			dcol = [0, 1, 0, -1]
			for i in range(len(drow)):
				nrow = x_cor + drow[i]
				ncol = y_cor + dcol[i]
				if nrow >= 0 and nrow < N and (ncol >= 0) and (ncol < M) and (visited[nrow][ncol] == 0):
					visited[nrow][ncol] = 1
					if grid[nrow][ncol] == 'Y':
						ans = min(ans, steps + 1)
					q.append([nrow, ncol, steps + 1])
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		x_pos = []
		y_pos = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					x_pos.append((i, j))
				elif grid[i][j] == 'Y':
					y_pos.append((i, j))
		min_dist = float('inf')
		for x in x_pos:
			for y in y_pos:
				dist = abs(x[0] - y[0]) + abs(x[1] - y[1])
				if dist < min_dist:
					min_dist = dist
					if min_dist == 1:
						return min_dist
		return min_dist


class Solution:

	def shortestXYDist(self, grid, N, M):
		minDist = M + N
		dist = M + N
		for i in range(N):
			if minDist == 1:
				break
			for j in range(M):
				if minDist == 1:
					break
				if grid[i][j] == 'X':
					for a in range(max(0, i - minDist), min(i + minDist, N)):
						for b in range(max(0, j - minDist), min(j + minDist, M)):
							if grid[a][b] == 'Y':
								dist = abs(i - a) + abs(j - b)
								if dist < minDist:
									minDist = dist
		return minDist


class Solution:

	def shortestXYDist(self, grid, N, M):
		visited = [[0 for i in range(M)] for j in range(N)]
		queue = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					queue.append([[i, j], 0])
					visited[i][j] = 1
		dr = [0, 0, -1, 1]
		dc = [1, -1, 0, 0]
		while len(queue) > 0:
			node = queue.pop(0)
			cr = node[0][0]
			cc = node[0][1]
			gap = node[1]
			if grid[cr][cc] == 'Y':
				return gap
			for k in range(4):
				nr = cr + dr[k]
				nc = cc + dc[k]
				if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (visited[nr][nc] == 0):
					queue.append([[nr, nc], gap + 1])
					visited[nr][nc] = 1
		return -1


def print2d(grid):
	(n, m) = (len(grid), len(grid[0]))
	for i in range(n):
		print(grid[i])
	print()

class Solution:

	def shortestXYDist(self, grid, N, M):
		(res, y_count) = (N * M + 1, 0)
		q = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append((i, j, 0))
				elif grid[i][j] == 'Y':
					y_count += 1
		if y_count == 0:
			return -1
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		while q:
			queue = []
			for ind in range(len(q)):
				(i, j, dist) = q[ind]
				if grid[i][j] == 'Z':
					continue
				grid[i][j] = 'Z'
				for k in range(4):
					(ii, jj) = (i + dx[k], j + dy[k])
					if ii >= 0 and ii < N and (jj >= 0) and (jj < M):
						if grid[ii][jj] == 'Y':
							return dist + 1
						queue.append((ii, jj, dist + 1))
			q = queue
		return res


def print2d(grid):
	(n, m) = (len(grid), len(grid[0]))
	for i in range(n):
		print(grid[i])
	print()

class Solution:

	def shortestXYDist(self, grid, N, M):
		dp = [[0] * M for i in range(N)]
		if grid[0][0] == 'X':
			dp[0][0] = 0
		else:
			dp[0][0] = N * M + 1
		res = N * M + 1
		for i in range(N):
			for j in range(M):
				if i == 0 and j == 0:
					continue
				if i == 0:
					dp[i][j] = dp[i][j - 1] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if j == 0:
					dp[i][j] = dp[i - 1][j] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
				if res == 1:
					return 1
		dp = [[0] * M for i in range(N)]
		if grid[N - 1][M - 1] == 'X':
			dp[N - 1][M - 1] = 0
		else:
			dp[N - 1][M - 1] = N * M + 1
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if i == N - 1 and j == M - 1:
					continue
				if i == N - 1:
					dp[i][j] = dp[i][j + 1] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if j == M - 1:
					dp[i][j] = dp[i + 1][j] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
				if res == 1:
					return 1
		dp = [[0] * M for i in range(N)]
		if grid[0][M - 1] == 'X':
			dp[0][M - 1] = 0
		else:
			dp[0][M - 1] = N * M + 1
		for i in range(N):
			for j in range(M - 1, -1, -1):
				if i == 0 and j == M - 1:
					continue
				if i == 0:
					dp[i][j] = dp[i][j + 1] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if j == M - 1:
					dp[i][j] = dp[i - 1][j] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					dp[i][j] = min(dp[i][j + 1], dp[i - 1][j]) + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
				if res == 1:
					return 1
		dp = [[0] * M for i in range(N)]
		if grid[N - 1][0] == 'X':
			dp[N - 1][0] = 0
		else:
			dp[N - 1][0] = N * M + 1
		for i in range(N - 1, -1, -1):
			for j in range(M):
				if i == N - 1 and j == 0:
					continue
				if i == N - 1:
					dp[i][j] = dp[i][j - 1] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if j == 0:
					dp[i][j] = dp[i + 1][j] + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
					elif grid[i][j] == 'X':
						dp[i][j] = 0
					continue
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1
					if grid[i][j] == 'Y':
						res = min(res, dp[i][j])
				if res == 1:
					return 1
		return res


from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		visited = set()
		q = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append([i, j, 0])
					visited.add((i, j))
		row = [1, 0, -1, 0]
		col = [0, 1, 0, -1]
		while q:
			(i, j, d) = q.popleft()
			if grid[i][j] == 'Y':
				return d
			for k in range(4):
				n = row[k] + i
				m = col[k] + j
				if 0 <= n < N and 0 <= m < M and ((n, m) not in visited):
					q.append([n, m, d + 1])
					visited.add((n, m))
		return 0


class Solution:

	def shortestXYDist(self, grid, N, M):
		q = []
		l = 0
		v = [[0] * M for _ in range(N)]
		for i in range(0, N):
			for j in range(0, M):
				if grid[i][j] == 'X':
					v[i][j] = 1
					q.append((i, j))
		while len(q) > 0:
			n = len(q)
			for i in range(0, n):
				(x, y) = q.pop(0)
				if grid[x][y] == 'Y':
					return l
				if x > 0 and v[x - 1][y] == 0:
					q.append((x - 1, y))
					v[x - 1][y] = 1
				if y > 0 and v[x][y - 1] == 0:
					q.append((x, y - 1))
					v[x][y - 1] = 1
				if x < N - 1 and v[x + 1][y] == 0:
					q.append((x + 1, y))
					v[x + 1][y] = 1
				if y < M - 1 and v[x][y + 1] == 0:
					q.append((x, y + 1))
					v[x][y + 1] = 1
			l += 1
		return -1


from numpy import inf
from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		check = lambda x, y: 0 <= x < N and 0 <= y < M
		dp = [[False] * M for _ in range(N)]
		queue = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					queue.append((i, j, 0))
					dp[i][j] = True
		res = inf
		while queue:
			(x, y, path) = queue.popleft()
			for (dx, dy) in moves:
				if check(x + dx, y + dy) and (not dp[x + dx][y + dy]):
					dp[x + dx][y + dy] = True
					if grid[x + dx][y + dy] == 'Y':
						res = min(res, path + 1)
					queue.append((x + dx, y + dy, path + 1))
		return res


class Solution:

	def shortestXYDist(self, grid, N, M):
		x_coordinates = []
		y_coordinates = []
		minDist = N * M
		for row in range(N):
			for col in range(M):
				if grid[row][col] == 'X':
					x_coordinates.append((row, col))
				elif grid[row][col] == 'Y':
					y_coordinates.append((row, col))
		for (R, C) in x_coordinates:
			for (r, c) in y_coordinates:
				minDist = min(minDist, abs(R - r) + abs(C - c))
				if minDist == 1:
					break
		return minDist


class Solution:

	def shortestXYDist(self, grid, N, M):
		ans = 1000000000.0
		x_lst = []
		y_lst = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					x_lst.append([i, j])
				elif grid[i][j] == 'Y':
					y_lst.append([i, j])
		for i in range(len(x_lst)):
			for j in range(len(y_lst)):
				ans = min(ans, abs(x_lst[i][0] - y_lst[j][0]) + abs(x_lst[i][1] - y_lst[j][1]))
			if ans == 1:
				return ans
		return ans


from math import inf
from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		dp = [[inf] * M for i in range(N)]
		que = deque([(i, j) for i in range(N) for j in range(M) if grid[i][j] == 'X'])
		change = [-1, 0, 1, 0, -1]
		while que:
			(x, y) = que.popleft()
			if grid[x][y] == 'X':
				if dp[x][y] != 0:
					dp[x][y] = 0
				else:
					continue
			for i in range(0, 4):
				(nx, ny) = (x + change[i], y + change[i + 1])
				if not (0 <= nx < N and 0 <= ny < M):
					continue
				if dp[nx][ny] > dp[x][y] + 1:
					dp[nx][ny] = dp[x][y] + 1
					que.append((nx, ny))
		ans = inf
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'Y':
					ans = min(ans, dp[i][j])
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		i = 0
		d = N * M
		col_idx_x = []
		col_idx_y = []
		while i < N:
			j = 0
			while j < M:
				if grid[i][j] == 'X':
					col_idx_x.append((i, j))
				elif grid[i][j] == 'Y':
					col_idx_y.append((i, j))
				j += 1
			i += 1
		for i in col_idx_x:
			for j in col_idx_y:
				dis = abs(i[0] - j[0]) + abs(i[1] - j[1])
				d = min(d, dis)
				if d == 1:
					break
		return d


from collections import deque

class Solution:

	def shortestXYDist(self, grid, N, M):
		dp = [[N * M + 1 for i in range(M)] for j in range(N)]
		ans = N * M + 2
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					mn = N * M + 1
					if i > 0:
						mn = min(mn, dp[i - 1][j] + 1)
					if j > 0:
						mn = min(mn, dp[i][j - 1] + 1)
					dp[i][j] = mn
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if grid[i][j] == 'X':
					dp[i][j] = 0
				else:
					mn = N * M + 1
					if i + 1 < N:
						mn = min(mn, dp[i + 1][j] + 1)
					if j + 1 < M:
						mn = min(mn, dp[i][j + 1] + 1)
					if mn != N * M + 1:
						dp[i][j] = min(mn, dp[i][j])
				if grid[i][j] == 'Y':
					ans = min(ans, dp[i][j])
		return ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		x_positions = []
		y_positions = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X':
					x_positions.append((i, j))
				elif grid[i][j] == 'Y':
					y_positions.append((i, j))
		min_distance = float('inf')
		for x in x_positions:
			for y in y_positions:
				distance = abs(x[0] - y[0]) + abs(x[1] - y[1])
				if distance < min_distance:
					min_distance = distance
					if min_distance == 1:
						return 1
		return min_distance


class Solution:

	def shortestXYDist(self, grid, N, M):
		ans = [[float('inf') for _ in range(M)] for _ in range(N)]
		for r in range(N):
			for c in range(M):
				if grid[r][c] == 'X':
					ans[r][c] = 0
				else:
					if r > 0:
						ans[r][c] = min(ans[r][c], ans[r - 1][c] + 1)
					if c > 0:
						ans[r][c] = min(ans[r][c], ans[r][c - 1] + 1)
		for r in range(N - 1, -1, -1):
			for c in range(M - 1, -1, -1):
				if grid[r][c] == 'X':
					ans[r][c] = 0
				else:
					if r < N - 1:
						ans[r][c] = min(ans[r][c], ans[r + 1][c] + 1)
					if c < M - 1:
						ans[r][c] = min(ans[r][c], ans[r][c + 1] + 1)
		min_ans = float('inf')
		for r in range(N):
			for c in range(M):
				if grid[r][c] == 'Y':
					min_ans = min(min_ans, ans[r][c])
		return min_ans


class Solution:

	def shortestXYDist(self, grid, N, M):
		dist = N + M - 2
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					if dist > N / 2 or dist > M / 2:
						for k in range(N):
							for l in range(M):
								if grid[k][l] == 'Y':
									temp = abs(k - i) + abs(l - j)
									if temp < dist:
										dist = temp
										if dist == 1:
											return 1
					else:
						for k in range(i - dist, i + dist + 1):
							if k < 0:
								continue
							if k >= N:
								break
							for l in range(j - dist, j + dist + 1):
								if l < 0:
									continue
								if l >= M:
									break
								if grid[k][l] == 'Y':
									temp = abs(k - i) + abs(l - j)
									if temp < dist:
										dist = temp
										if dist == 1:
											return 1
		return dist


class Solution:

	def shortestXYDist(self, grid, N, M):
		X_coordinates = []
		Y_coordinates = []
		minDist = N * M
		for row in range(N):
			for col in range(M):
				if grid[row][col] == 'X':
					X_coordinates.append((row, col))
				elif grid[row][col] == 'Y':
					Y_coordinates.append((row, col))
		for (Row, Col) in X_coordinates:
			for (row, column) in Y_coordinates:
				minDist = min(minDist, abs(Row - row) + abs(Col - column))
				if minDist == 1:
					break
		return minDist


class Solution:

	def shortestXYDist(self, grid, N, M):
		X = []
		Y = []
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					X.append([i, j])
				elif grid[i][j] == 'Y':
					Y.append([i, j])
		mn = N + M + 1
		for a in X:
			for b in Y:
				mn = min(mn, abs(a[0] - b[0]) + abs(a[1] - b[1]))
				if mn == 1:
					break
		return mn


class Solution:

	def shortestXYDist(self, grid, N, M):
		q = []
		vis = [[False for _ in range(M)] for _ in range(N)]
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 'X':
					q.append((i, j, 0))
					vis[i][j] = True
		dirt = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		while len(q):
			(i, j, gap) = q.pop(0)
			if grid[i][j] == 'Y':
				return gap
			for (x, y) in dirt:
				dx = i + x
				dy = j + y
				if 0 <= dx < N and 0 <= dy < M and (vis[dx][dy] == False):
					q.append((dx, dy, gap + 1))
					vis[dx][dy] = True
		return -1