solutions: ["class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvis = [[-1] * (N + 1) for i in range(N + 1)]\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tq = [(KnightPos[0], KnightPos[1], 0)]\n\t\tvis[KnightPos[0]][KnightPos[1]] = 0\n\t\td = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, -2], [-1, 2]]\n\t\twhile q:\n\t\t\t(x, y, step) = q.pop(0)\n\t\t\tfor (i, j) in d:\n\t\t\t\tr = x + i\n\t\t\t\tc = y + j\n\t\t\t\tif [r, c] == TargetPos:\n\t\t\t\t\treturn step + 1\n\t\t\t\tif 0 <= r <= N and 0 <= c <= N and (vis[r][c] == -1):\n\t\t\t\t\tq.append([r, c, step + 1])\n\t\t\t\t\tvis[r][c] = step + 1\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\n\t\tclass Cell:\n\n\t\t\tdef __init__(self, x=0, y=0, dist=0):\n\t\t\t\tself.x = x\n\t\t\t\tself.y = y\n\t\t\t\tself.dist = dist\n\n\t\tdef isInside(x, y, N):\n\t\t\tif x >= 1 and x <= N and (y >= 1) and (y <= N):\n\t\t\t\treturn True\n\t\t\treturn False\n\t\tdx = [2, 2, -2, -2, 1, 1, -1, -1]\n\t\tdy = [1, -1, 1, -1, 2, -2, 2, -2]\n\t\tqueue = []\n\t\tqueue.append(Cell(KnightPos[0], KnightPos[1], 0))\n\t\tvisited = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tvisited[KnightPos[0]][KnightPos[1]] = True\n\t\twhile len(queue) > 0:\n\t\t\tt = queue[0]\n\t\t\tqueue.pop(0)\n\t\t\tif t.x == TargetPos[0] and t.y == TargetPos[1]:\n\t\t\t\treturn t.dist\n\t\t\tfor i in range(8):\n\t\t\t\tx = t.x + dx[i]\n\t\t\t\ty = t.y + dy[i]\n\t\t\t\tif isInside(x, y, N) and (not visited[x][y]):\n\t\t\t\t\tvisited[x][y] = True\n\t\t\t\t\tqueue.append(Cell(x, y, t.dist + 1))\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tfrom collections import deque\n\n\t\tdef isVisited(X, Y):\n\t\t\treturn '{}_{}'.format(X, Y) in visitedCells\n\t\tmoveDelta = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))\n\t\tdist = [[0 for i in range(N)] for j in range(N)]\n\t\tQ = deque()\n\t\tvisitedCells = set()\n\t\t(xInit, yInit) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\t(xFinal, yFinal) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\tQ.append((xInit, yInit))\n\t\tvisitedCells.add('{}_{}'.format(xInit, yInit))\n\t\twhile Q:\n\t\t\t(xCur, yCur) = Q.popleft()\n\t\t\tif xCur == xFinal and yCur == yFinal:\n\t\t\t\treturn dist[xCur][yCur]\n\t\t\tfor (xDel, yDel) in moveDelta:\n\t\t\t\t(xNext, yNext) = (xCur + xDel, yCur + yDel)\n\t\t\t\tif 0 <= xNext < N and 0 <= yNext < N and (not isVisited(xNext, yNext)):\n\t\t\t\t\tdist[xNext][yNext] = dist[xCur][yCur] + 1\n\t\t\t\t\tvisitedCells.add('{}_{}'.format(xNext, yNext))\n\t\t\t\t\tQ.append((xNext, yNext))\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N) -> int:\n\t\tans = 0\n\t\tdx = [-2, -1, 1, 2, -2, -1, 1, 2]\n\t\tdy = [-1, -2, -2, -1, 1, 2, 2, 1]\n\t\tq = deque()\n\t\tq.append(KnightPos)\n\t\tvisited = set()\n\t\tvisited.add(','.join(map(str, KnightPos)))\n\t\twhile q:\n\t\t\tsz = len(q)\n\t\t\twhile sz:\n\t\t\t\tsz -= 1\n\t\t\t\tcur = q.popleft()\n\t\t\t\tif cur == TargetPos:\n\t\t\t\t\treturn ans\n\t\t\t\tfor i in range(8):\n\t\t\t\t\t(nx, ny) = (cur[0] + dx[i], cur[1] + dy[i])\n\t\t\t\t\tnstr = ','.join(map(str, [nx, ny]))\n\t\t\t\t\tif nx > 0 and nx <= N and (ny > 0) and (ny <= N) and (nstr not in visited):\n\t\t\t\t\t\tvisited.add(nstr)\n\t\t\t\t\t\tq.append([nx, ny])\n\t\t\tans += 1\n\t\treturn ans\n", "from queue import Queue\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = Queue(maxsize=2 + N * N)\n\t\tvis = [[0 for i in range(N)] for j in range(N)]\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\tTargetPos[0] -= 1\n\t\tTargetPos[1] -= 1\n\t\tlevel = [[0 for i in range(N)] for j in range(N)]\n\n\t\tdef ifpos(r, c):\n\t\t\tif not (r >= 0 and c >= 0 and (r < N) and (c < N)):\n\t\t\t\treturn False\n\t\t\telif vis[r][c] == 1:\n\t\t\t\treturn False\n\t\t\telse:\n\t\t\t\treturn True\n\n\t\tdef bfs(kn):\n\t\t\tops = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [1, -2], [-1, 2], [1, 2]]\n\t\t\tq.put(kn)\n\t\t\tvis[kn[0]][kn[1]] = 1\n\t\t\twhile not q.empty():\n\t\t\t\t(r, c) = q.get()\n\t\t\t\tif TargetPos == [r, c]:\n\t\t\t\t\treturn level[r][c]\n\t\t\t\telse:\n\t\t\t\t\tfor i in ops:\n\t\t\t\t\t\tif ifpos(r + i[0], c + i[1]):\n\t\t\t\t\t\t\tq.put([r + i[0], c + i[1]])\n\t\t\t\t\t\t\tvis[r + i[0]][c + i[1]] = 1\n\t\t\t\t\t\t\tlevel[r + i[0]][c + i[1]] = level[r][c] + 1\n\t\tans = bfs(KnightPos)\n\t\treturn ans\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = deque()\n\t\tq.append(KnightPos)\n\t\tdistance = [[-1 for i in range(N + 1)] for j in range(N + 1)]\n\t\tvisited = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tdistance[KnightPos[0]][KnightPos[1]] = 0\n\t\twhile len(q) > 0:\n\t\t\t(pop_x, pop_y) = q.popleft()\n\t\t\tx = [-2, -2, -1, 1, 2, 2, 1, -1]\n\t\t\ty = [-1, 1, 2, 2, 1, -1, -2, -2]\n\t\t\tfor i in range(8):\n\t\t\t\tx_val = x[i] + pop_x\n\t\t\t\ty_val = pop_y + y[i]\n\t\t\t\tif x_val > N or y_val > N or x_val <= 0 or (y_val <= 0) or (distance[x_val][y_val] != -1):\n\t\t\t\t\tcontinue\n\t\t\t\tdistance[x_val][y_val] = 1 + distance[pop_x][pop_y]\n\t\t\t\tq.append([x_val, y_val])\n\t\treturn distance[TargetPos[0]][TargetPos[1]]\n", "from collections import *\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tkx = KnightPos[0] - 1\n\t\tky = KnightPos[1] - 1\n\t\ttx = TargetPos[0] - 1\n\t\tty = TargetPos[1] - 1\n\t\tans = 0\n\n\t\tdef isvalid(x, y, visit, N):\n\t\t\tif x >= 0 and y >= 0 and (x < N) and (y < N) and (visit[x][y] == False):\n\t\t\t\treturn True\n\t\t\treturn False\n\t\tif kx == tx and ty == ky:\n\t\t\treturn ans\n\t\tmoves = [[-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2]]\n\t\tvisit = [[False for i in range(N)] for j in range(N)]\n\t\tq = deque([[kx, ky]])\n\t\tvisit[kx][ky] = True\n\t\twhile q:\n\t\t\tans += 1\n\t\t\tsize = len(q)\n\t\t\tfor i in range(size):\n\t\t\t\t(kx, ky) = q.popleft()\n\t\t\t\tfor (m, n) in moves:\n\t\t\t\t\tif kx + m == tx and ky + n == ty:\n\t\t\t\t\t\treturn ans\n\t\t\t\t\tif isvalid(kx + m, ky + n, visit, N):\n\t\t\t\t\t\tvisit[kx + m][ky + n] = True\n\t\t\t\t\t\tq.append([kx + m, ky + n])\n\t\treturn ans\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvis = [[0] * N for i in range(N)]\n\t\tdirec = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]\n\n\t\tdef bfs(i, j, s):\n\t\t\tq = [[i, j, s]]\n\t\t\twhile q:\n\t\t\t\t(t1, t2, d) = q.pop(0)\n\t\t\t\tif t1 == TargetPos[0] - 1 and t2 == TargetPos[1] - 1:\n\t\t\t\t\treturn d\n\t\t\t\tfor i in range(len(direc)):\n\t\t\t\t\t(t3, t4) = direc[i]\n\t\t\t\t\tif 0 <= t1 + t3 < N and 0 <= t2 + t4 < N and (vis[t1 + t3][t2 + t4] == 0):\n\t\t\t\t\t\tvis[t1 + t3][t2 + t4] = 1\n\t\t\t\t\t\tq.append([t1 + t3, t2 + t4, d + 1])\n\t\t\treturn -1\n\t\treturn bfs(KnightPos[0] - 1, KnightPos[1] - 1, 0)\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tque = []\n\t\tvisited = []\n\t\tww = KnightPos[0]\n\t\tww1 = KnightPos[1]\n\t\tfor i in range(0, N + 1):\n\t\t\tax = [False] * (N + 1)\n\t\t\tvisited.append(ax)\n\t\tque.append([KnightPos[0], KnightPos[1], 0])\n\t\tvisited[ww][ww1]\n\t\tvisited\n\t\tanss = 1000000\n\t\trow = [-1, -2, -2, -1, 1, 2, 2, 1]\n\t\tcol = [-2, -1, 1, 2, 2, 1, -1, -2]\n\t\tfinal = TargetPos[0]\n\t\tfinal1 = TargetPos[1]\n\t\twhile len(que) != 0:\n\t\t\ta = que[0][0]\n\t\t\tb = que[0][1]\n\t\t\tc = que[0][2]\n\t\t\tque.pop(0)\n\t\t\tif a == final and b == final1 and (c < anss):\n\t\t\t\tanss = c\n\t\t\tfor i in range(0, 8):\n\t\t\t\tfinrow = a + row[i]\n\t\t\t\tfincol = b + col[i]\n\t\t\t\tif finrow > 0 and finrow < N + 1 and (fincol > 0) and (fincol < N + 1) and (visited[finrow][fincol] == False):\n\t\t\t\t\tque.append([finrow, fincol, c + 1])\n\t\t\t\t\tvisited[finrow][fincol] = True\n\t\treturn anss\n", "class QueueNode:\n\n\tdef __init__(self, x, y, d=0):\n\t\tself.x = x\n\t\tself.y = y\n\t\tself.d = d\n\ndef isValid(i, j, N, M):\n\treturn i >= 1 and i <= N and (j >= 1) and (j <= M)\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tM = N\n\t\t(i, j) = KnightPos\n\t\t(X, Y) = TargetPos\n\t\tvisited = [[False for _ in range(M + 1)] for _ in range(N + 1)]\n\t\tstart = QueueNode(i, j)\n\t\tvisited[i][j] = True\n\t\tq = [start]\n\t\tdirj = [-1, -2, -2, -1, 1, 2, 2, 1]\n\t\tdiri = [-2, -1, 1, 2, 2, 1, -1, -2]\n\t\twhile len(q) != 0:\n\t\t\tcurr = q.pop(0)\n\t\t\t(x, y, d) = (curr.x, curr.y, curr.d)\n\t\t\tif x == X and y == Y:\n\t\t\t\treturn d\n\t\t\tfor k in range(8):\n\t\t\t\tnexti = x + diri[k]\n\t\t\t\tnextj = y + dirj[k]\n\t\t\t\tif isValid(nexti, nextj, N, M) and (not visited[nexti][nextj]):\n\t\t\t\t\tq.append(QueueNode(nexti, nextj, d + 1))\n\t\t\t\t\tvisited[nexti][nextj] = True\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(r, c) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\tq = [(r, c, 0)]\n\t\tvisited = set()\n\t\tvisited.add((r, c))\n\t\trow = [-2, -2, -1, -1, 1, 1, 2, 2]\n\t\tcol = [-1, 1, -2, 2, -2, 2, -1, 1]\n\t\twhile q:\n\t\t\t(r, c, move) = q.pop(0)\n\t\t\tif r == TargetPos[0] - 1 and c == TargetPos[1] - 1:\n\t\t\t\treturn move\n\t\t\tfor i in range(len(row)):\n\t\t\t\tnextr = r + row[i]\n\t\t\t\tnextc = c + col[i]\n\t\t\t\tif (nextr, nextc) not in visited and nextr >= 0 and (nextc >= 0) and (nextr < N) and (nextc < N):\n\t\t\t\t\tvisited.add((nextr, nextc))\n\t\t\t\t\tq.append((nextr, nextc, move + 1))\n", "import sys\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\trow = [-2, -2, 2, 2, 1, 1, -1, -1]\n\t\tcol = [-1, 1, -1, 1, -2, 2, 2, -2]\n\t\t(sr, sc) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\t(tr, tc) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\tvis = set()\n\t\tvis.add((sr, sc))\n\t\tdis = 0\n\t\tq = [(sr, sc, dis)]\n\t\twhile q:\n\t\t\t(sr, sc, dis) = q.pop(0)\n\t\t\tif sr == tr and sc == tc:\n\t\t\t\treturn dis\n\t\t\tfor i in range(8):\n\t\t\t\tnr = sr + row[i]\n\t\t\t\tnc = sc + col[i]\n\t\t\t\tif nr >= 0 and nc >= 0 and (nr < N) and (nc < N) and ((nr, nc) not in vis):\n\t\t\t\t\tvis.add((nr, nc))\n\t\t\t\t\tq.append((nr, nc, dis + 1))\n\t\treturn dis\n", "def shortest_path(source_pos, target_pos, n):\n\tboard_arr = [[0] * n for i in range(n)]\n\tsource_row = n - source_pos[1]\n\tsource_col = source_pos[0] - 1\n\ttarget_row = n - target_pos[1]\n\ttarget_col = target_pos[0] - 1\n\tif source_row == target_row and source_col == target_col:\n\t\treturn 0\n\tdata_queue = [[source_row, source_col]]\n\tmove_x = [2, 2, 1, 1, -1, -1, -2, -2]\n\tmove_y = [1, -1, 2, -2, 2, -2, 1, -1]\n\twhile len(data_queue) > 0:\n\t\tdata = data_queue.pop(0)\n\t\trow = data[0]\n\t\tcol = data[1]\n\t\tfor i in range(8):\n\t\t\tnew_row = row + move_y[i]\n\t\t\tnew_col = col + move_x[i]\n\t\t\tif is_safe(board_arr, n, new_row, new_col, source_row, source_col):\n\t\t\t\tboard_arr[new_row][new_col] = board_arr[row][col] + 1\n\t\t\t\tdata_queue.append([new_row, new_col])\n\treturn board_arr[target_row][target_col]\n\ndef is_safe(board_arr: [[]], n, row, col, source_row, source_col):\n\tif row == source_row and col == source_col:\n\t\treturn False\n\tif row < 0 or row >= n:\n\t\treturn False\n\tif col < 0 or col >= n:\n\t\treturn False\n\tif board_arr[row][col] != 0:\n\t\treturn False\n\treturn True\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\treturn shortest_path(KnightPos, TargetPos, N)\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\n\t\tdef isValid(x, y, n):\n\t\t\tif x >= 0 and x < n and (y >= 0) and (y < n):\n\t\t\t\treturn True\n\t\t\treturn False\n\t\tqueue = []\n\t\ttpos = [TargetPos[0] - 1, TargetPos[1] - 1]\n\t\tkpos = [KnightPos[0] - 1, KnightPos[1] - 1]\n\t\tvisited = [[False for i in range(N)] for i in range(N)]\n\t\tqueue.append(kpos)\n\t\tqueue.append('END')\n\t\tvisited[kpos[0]][kpos[1]] = True\n\t\tans = 0\n\t\twhile len(queue) > 0:\n\t\t\tif queue[0] == 'END':\n\t\t\t\tqueue.pop(0)\n\t\t\t\tans += 1\n\t\t\t\tif len(queue) > 0:\n\t\t\t\t\tqueue.append('END')\n\t\t\telif queue[0] == tpos:\n\t\t\t\treturn ans\n\t\t\telse:\n\t\t\t\ttemp = queue.pop(0)\n\t\t\t\tx = [1, 2, 2, 1, -1, -2, -2, -1]\n\t\t\t\ty = [2, 1, -1, -2, -2, -1, 1, 2]\n\t\t\t\tfor i in range(8):\n\t\t\t\t\tif isValid(temp[0] + x[i], temp[1] + y[i], N) and visited[temp[0] + x[i]][temp[1] + y[i]] == False:\n\t\t\t\t\t\tif [temp[0] + x[i], temp[1] + y[i]] == tpos:\n\t\t\t\t\t\t\treturn ans + 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tqueue.append([temp[0] + x[i], temp[1] + y[i]])\n\t\t\t\t\t\t\tvisited[temp[0] + x[i]][temp[1] + y[i]] = True\n\t\treturn ans\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = [(*KnightPos, 0)]\n\t\tvisited = {tuple(KnightPos)}\n\t\tdx = [2, 2, -2, -2, 1, 1, -1, -1]\n\t\tdy = [1, -1, 1, -1, 2, -2, 2, -2]\n\t\twhile len(q):\n\t\t\tq2 = []\n\t\t\tfor (x, y, d) in q:\n\t\t\t\tif TargetPos == [x, y]:\n\t\t\t\t\treturn d\n\t\t\t\tfor i in range(8):\n\t\t\t\t\txx = x + dx[i]\n\t\t\t\t\tyy = y + dy[i]\n\t\t\t\t\tif (xx, yy) not in visited:\n\t\t\t\t\t\tvisited.add((xx, yy))\n\t\t\t\t\t\tq2.append((xx, yy, d + 1))\n\t\t\tq = q2\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, kpos, tpos, n):\n\t\tvis = set()\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\tif kpos[0] == i and kpos[1] == j:\n\t\t\t\t\tq = []\n\t\t\t\t\tsteps = 0\n\t\t\t\t\tq.append((i, j, steps))\n\t\t\t\t\tvis.add((i, j))\n\t\t\t\t\twhile q:\n\t\t\t\t\t\t(row, col, c) = q.pop(0)\n\t\t\t\t\t\tif row == tpos[0] and col == tpos[1]:\n\t\t\t\t\t\t\treturn c\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tfor (r, c1) in [[-1, 2], [-1, -2], [1, 2], [1, -2], [-2, -1], [-2, 1], [2, -1], [2, 1]]:\n\t\t\t\t\t\t\t\tnrow = r + row\n\t\t\t\t\t\t\t\tncol = c1 + col\n\t\t\t\t\t\t\t\tif 1 <= nrow < n + 1 and 1 <= ncol < n + 1 and ((nrow, ncol) not in vis):\n\t\t\t\t\t\t\t\t\tq.append((nrow, ncol, c + 1))\n\t\t\t\t\t\t\t\t\tvis.add((nrow, ncol))\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tq = []\n\t\tq.append((KnightPos[0] - 1, KnightPos[1] - 1))\n\t\tdr = [1, 2, 1, 2, -1, -2, -1, -2]\n\t\tdc = [2, 1, -2, -1, -2, -1, 2, 1]\n\t\tvisited = set()\n\t\tmoves = 0\n\t\twhile q:\n\t\t\tcount = len(q)\n\t\t\tmoves += 1\n\t\t\twhile count:\n\t\t\t\tcurr = q.pop(0)\n\t\t\t\tfor i in range(8):\n\t\t\t\t\tr = curr[0] + dr[i]\n\t\t\t\t\tc = curr[1] + dc[i]\n\t\t\t\t\tif r < 0 or c < 0 or r >= N or (c >= N):\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif (r, c) in visited:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif r == TargetPos[0] - 1 and c == TargetPos[1] - 1:\n\t\t\t\t\t\treturn moves\n\t\t\t\t\tq.append((r, c))\n\t\t\t\t\tvisited.add((r, c))\n\t\t\t\tcount -= 1\n\t\treturn -1\n", "class Solution:\n\n\tdef __init__(self):\n\t\tself.dis = 0\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\trow = [-2, -2, 2, 2, 1, 1, -1, -1]\n\t\tcol = [-1, 1, -1, 1, -2, 2, 2, -2]\n\t\t(sr, sc) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\t(tr, tc) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\t(rows, cols) = (N, N)\n\t\tvis = [[0 for i in range(N)] for j in range(N)]\n\t\tvis[sr][sc] = 1\n\t\tdis = 0\n\t\tq = [(sr, sc, dis)]\n\t\twhile q:\n\t\t\t(sr, sc, dis) = q.pop(0)\n\t\t\tif sr == tr and sc == tc:\n\t\t\t\treturn dis\n\t\t\tfor i in range(8):\n\t\t\t\tnr = sr + row[i]\n\t\t\t\tnc = sc + col[i]\n\t\t\t\tif nr >= 0 and nc >= 0 and (nr < rows) and (nc < cols) and (vis[nr][nc] == 0):\n\t\t\t\t\tvis[nr][nc] = 1\n\t\t\t\t\tq.append((nr, nc, dis + 1))\n\t\treturn dis\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisited = [[False for _ in range(N)] for _ in range(N)]\n\t\td = [[-1 for _ in range(N)] for _ in range(N)]\n\t\tvisited[N - KnightPos[1]][KnightPos[0] - 1] = True\n\t\td[N - KnightPos[1]][KnightPos[0] - 1] = 0\n\t\tQ = deque()\n\t\tQ.append((N - KnightPos[1], KnightPos[0] - 1))\n\t\twhile Q:\n\t\t\t(i, j) = Q.popleft()\n\t\t\tfor (u, w) in [(-2, -1), (-1, -2), (-2, 1), (-1, 2), (1, -2), (2, -1), (2, 1), (1, 2)]:\n\t\t\t\tif 0 <= i + u < N and 0 <= j + w < N:\n\t\t\t\t\tif not visited[i + u][j + w]:\n\t\t\t\t\t\tvisited[i + u][j + w] = True\n\t\t\t\t\t\td[i + u][j + w] = d[i][j] + 1\n\t\t\t\t\t\tQ.append((i + u, j + w))\n\t\treturn d[N - TargetPos[1]][TargetPos[0] - 1]\n", "from queue import Queue\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\n\t\tdef isval(a, b, N, visited):\n\t\t\treturn a >= 0 and a < N and (b >= 0) and (b < N) and (visited[a][b] == False)\n\t\tdirection = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]\n\t\tta = TargetPos[0] - 1\n\t\ttb = TargetPos[1] - 1\n\t\ta = KnightPos[0] - 1\n\t\tb = KnightPos[1] - 1\n\t\tif ta == a and tb == b:\n\t\t\treturn 0\n\t\tvisited = []\n\t\tfor i in range(N):\n\t\t\tvisited.append([False for i in range(N)])\n\t\tq = Queue()\n\t\tq.put([a, b, 0])\n\t\tvisited[a][b] = True\n\t\twhile not q.empty():\n\t\t\t(a, b, d) = q.get()\n\t\t\tif a == ta and b == tb:\n\t\t\t\treturn d\n\t\t\tfor (u, v) in direction:\n\t\t\t\tm = a + u\n\t\t\t\tn = b + v\n\t\t\t\tif isval(m, n, N, visited):\n\t\t\t\t\tq.put([m, n, d + 1])\n\t\t\t\t\tvisited[m][n] = True\n\t\treturn -1\n", "class Solution:\n\n\tdef isvalid(self, i, j, n, visited):\n\t\treturn i >= 0 and j >= 0 and (i < n) and (j < n) and (visited[i][j] == False)\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tfrom collections import deque\n\t\tq = deque()\n\t\tvisited = [[False for i in range(N)] for j in range(N)]\n\t\tq.append([KnightPos[0] - 1, KnightPos[1] - 1, 0])\n\t\tvisited[KnightPos[0] - 1][KnightPos[1] - 1] = True\n\t\tstep = 1\n\t\trow = [2, -2, 2, -2, 1, -1, 1, -1]\n\t\tcol = [1, -1, -1, 1, 2, -2, -2, 2]\n\t\twhile len(q) > 0:\n\t\t\tnode = q.popleft()\n\t\t\tif node[0] == TargetPos[0] - 1 and node[1] == TargetPos[1] - 1:\n\t\t\t\treturn node[2]\n\t\t\tfor i in range(8):\n\t\t\t\tnrow = node[0] + row[i]\n\t\t\t\tncol = node[1] + col[i]\n\t\t\t\tif self.isvalid(nrow, ncol, N, visited):\n\t\t\t\t\tvisited[nrow][ncol] = True\n\t\t\t\t\tq.append([nrow, ncol, node[2] + 1])\n\t\treturn -1\n", "from queue import Queue\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\n\t\tdef isValid(x, y, N, visited):\n\t\t\treturn x >= 0 and x < N and (y >= 0) and (y < N) and (visited[x][y] == False)\n\t\tdirec = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]\n\t\ttx = TargetPos[0] - 1\n\t\tty = TargetPos[1] - 1\n\t\tx = KnightPos[0] - 1\n\t\ty = KnightPos[1] - 1\n\t\tif tx == x and ty == y:\n\t\t\treturn 0\n\t\tvisited = []\n\t\tfor i in range(N):\n\t\t\tvisited.append([False for i in range(N)])\n\t\tq = Queue()\n\t\tq.put([x, y, 0])\n\t\tvisited[x][y] = True\n\t\twhile not q.empty():\n\t\t\t(x, y, d) = q.get()\n\t\t\tif x == tx and y == ty:\n\t\t\t\treturn d\n\t\t\tfor (u, v) in direc:\n\t\t\t\tp = x + u\n\t\t\t\tr = y + v\n\t\t\t\tif isValid(p, r, N, visited):\n\t\t\t\t\tq.put([p, r, d + 1])\n\t\t\t\t\tvisited[p][r] = True\n\t\treturn -1\n", "import numpy as np\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisitedpos = []\n\t\tsteps = []\n\t\tvisitedpos.append(KnightPos)\n\t\tsteps.append(0)\n\t\tvisited = np.zeros([N + 1, N + 1])\n\t\tmina = N + 1\n\t\twhile len(visitedpos) > 0:\n\t\t\tcurr = visitedpos.pop(0)\n\t\t\t(curr_x, curr_y) = (curr[0], curr[1])\n\t\t\tcurr_step = steps.pop(0)\n\t\t\tif curr_x == TargetPos[0] and curr_y == TargetPos[1]:\n\t\t\t\tmina = min(mina, curr_step)\n\t\t\tif curr_x + 2 < N + 1 and curr_y + 1 < N + 1 and (visited[curr_x + 2, curr_y + 1] == 0):\n\t\t\t\tvisitedpos.append([curr_x + 2, curr_y + 1])\n\t\t\t\tvisited[curr_x + 2, curr_y + 1] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x + 2 < N + 1 and curr_y - 1 > 0 and (visited[curr_x + 2, curr_y - 1] == 0):\n\t\t\t\tvisitedpos.append([curr_x + 2, curr_y - 1])\n\t\t\t\tvisited[curr_x + 2, curr_y - 1] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x - 2 > 0 and curr_y + 1 < N + 1 and (visited[curr_x - 2][curr_y + 1] == 0):\n\t\t\t\tvisitedpos.append([curr_x - 2, curr_y + 1])\n\t\t\t\tvisited[curr_x - 2, curr_y + 1] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x - 2 > 0 and curr_y - 1 > 0 and (visited[curr_x - 2][curr_y - 1] == 0):\n\t\t\t\tvisitedpos.append([curr_x - 2, curr_y - 1])\n\t\t\t\tvisited[curr_x - 2, curr_y - 1] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x + 1 < N + 1 and curr_y + 2 < N + 1 and (visited[curr_x + 1][curr_y + 2] == 0):\n\t\t\t\tvisitedpos.append([curr_x + 1, curr_y + 2])\n\t\t\t\tvisited[curr_x + 1, curr_y + 2] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x + 1 < N + 1 and curr_y - 2 > 0 and (visited[curr_x + 1][curr_y - 2] == 0):\n\t\t\t\tvisitedpos.append([curr_x + 1, curr_y - 2])\n\t\t\t\tvisited[curr_x + 1, curr_y - 2] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x - 1 > 0 and curr_y + 2 < N + 1 and (visited[curr_x - 1][curr_y + 2] == 0):\n\t\t\t\tvisitedpos.append([curr_x - 1, curr_y + 2])\n\t\t\t\tvisited[curr_x - 1, curr_y + 2] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\t\tif curr_x - 1 > 0 and curr_y - 2 > 0 and (visited[curr_x - 1][curr_y - 2] == 0):\n\t\t\t\tvisitedpos.append([curr_x - 1, curr_y - 2])\n\t\t\t\tvisited[curr_x - 1, curr_y - 2] = 1\n\t\t\t\tsteps.append(curr_step + 1)\n\t\treturn mina\n", "from collections import deque\n\nclass Solution:\n\n\tdef isValid(self, i, j, N):\n\t\tif i > 0 and j > 0 and (i <= N) and (j <= N):\n\t\t\treturn True\n\t\treturn False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = deque()\n\t\tvis = [[0] * (N + 1) for _ in range(N + 1)]\n\t\tdr = [-2, -2, -1, -1, 1, 1, 2, 2]\n\t\tdc = [1, -1, 2, -2, 2, -2, 1, -1]\n\t\tq.append([KnightPos[0], KnightPos[1], 0])\n\t\tvis[KnightPos[0]][KnightPos[1]] = 1\n\t\twhile len(q) != 0:\n\t\t\t(i, j, steps) = q.popleft()\n\t\t\tif TargetPos[0] == i and TargetPos[1] == j:\n\t\t\t\treturn steps\n\t\t\tfor k in range(0, 8):\n\t\t\t\tni = i + dr[k]\n\t\t\t\tnj = j + dc[k]\n\t\t\t\tif self.isValid(ni, nj, N) and vis[ni][nj] == 0:\n\t\t\t\t\tvis[ni][nj] = 1\n\t\t\t\t\tq.append([ni, nj, steps + 1])\n\t\treturn -1\n", "import math\nfrom collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tgrid = [[0 for i in range(N)] for j in range(N)]\n\t\tm = N\n\t\tn = N\n\t\ti = KnightPos[1] - 1\n\t\tj = KnightPos[0] - 1\n\t\tgrid[i][j] = 1\n\t\tq = deque()\n\t\tq.append([i, j])\n\t\ti = TargetPos[1] - 1\n\t\tj = TargetPos[0] - 1\n\t\tgrid[i][j] = -1\n\t\tcount = 0\n\t\twhile len(q) != 0:\n\t\t\ttemp_q = deque()\n\t\t\twhile len(q) != 0:\n\t\t\t\tidx = q.popleft()\n\t\t\t\ti = idx[0]\n\t\t\t\tj = idx[1]\n\t\t\t\tif i - 2 >= 0:\n\t\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\t\tif grid[i - 2][j - 1] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i - 2][j - 1] == 0:\n\t\t\t\t\t\t\tgrid[i - 2][j - 1] = 1\n\t\t\t\t\t\t\ttemp_q.append([i - 2, j - 1])\n\t\t\t\t\tif j + 1 < n:\n\t\t\t\t\t\tif grid[i - 2][j + 1] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i - 2][j + 1] == 0:\n\t\t\t\t\t\t\tgrid[i - 2][j + 1] = 1\n\t\t\t\t\t\t\ttemp_q.append([i - 2, j + 1])\n\t\t\t\tif j - 2 >= 0:\n\t\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\t\tif grid[i - 1][j - 2] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i - 1][j - 2] == 0:\n\t\t\t\t\t\t\tgrid[i - 1][j - 2] = 1\n\t\t\t\t\t\t\ttemp_q.append([i - 1, j - 2])\n\t\t\t\t\tif i + 1 < m:\n\t\t\t\t\t\tif grid[i + 1][j - 2] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i + 1][j - 2] == 0:\n\t\t\t\t\t\t\tgrid[i + 1][j - 2] = 1\n\t\t\t\t\t\t\ttemp_q.append([i + 1, j - 2])\n\t\t\t\tif i + 2 < m:\n\t\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\t\tif grid[i + 2][j - 1] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i + 2][j - 1] == 0:\n\t\t\t\t\t\t\tgrid[i + 2][j - 1] = 1\n\t\t\t\t\t\t\ttemp_q.append([i + 2, j - 1])\n\t\t\t\t\tif j + 1 < n:\n\t\t\t\t\t\tif grid[i + 2][j + 1] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i + 2][j + 1] == 0:\n\t\t\t\t\t\t\tgrid[i + 2][j + 1] = 1\n\t\t\t\t\t\t\ttemp_q.append([i + 2, j + 1])\n\t\t\t\tif j + 2 < n:\n\t\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\t\tif grid[i - 1][j + 2] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i - 1][j + 2] == 0:\n\t\t\t\t\t\t\tgrid[i - 1][j + 2] = 1\n\t\t\t\t\t\t\ttemp_q.append([i - 1, j + 2])\n\t\t\t\t\tif i + 1 < m:\n\t\t\t\t\t\tif grid[i + 1][j + 2] == -1:\n\t\t\t\t\t\t\treturn count + 1\n\t\t\t\t\t\telif grid[i + 1][j + 2] == 0:\n\t\t\t\t\t\t\tgrid[i + 1][j + 2] = 1\n\t\t\t\t\t\t\ttemp_q.append([i + 1, j + 2])\n\t\t\tq = temp_q.copy()\n\t\t\tcount += 1\n\t\treturn 0\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tq = deque([])\n\t\tvisited = set()\n\t\tminSteps = 0\n\t\t(r1, c1) = KnightPos\n\t\tq.append((r1, c1))\n\t\tvisited.add((r1, c1))\n\t\twhile q:\n\t\t\tfor i in range(len(q)):\n\t\t\t\t(r, c) = q.popleft()\n\t\t\t\tdirections = [[r - 1, c + 2], [r + 1, c + 2], [r - 1, c - 2], [r + 1, c - 2], [r - 2, c + 1], [r - 2, c - 1], [r + 2, c + 1], [r + 2, c - 1]]\n\t\t\t\tfor (nr, nc) in directions:\n\t\t\t\t\tif 1 <= nr <= N and 1 <= nc <= N and ((nr, nc) not in visited):\n\t\t\t\t\t\tif nr == TargetPos[0] and nc == TargetPos[1]:\n\t\t\t\t\t\t\treturn minSteps + 1\n\t\t\t\t\t\tq.append((nr, nc))\n\t\t\t\t\t\tvisited.add((nr, nc))\n\t\t\tminSteps += 1\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef check(self, N, x, y):\n\t\tif 0 <= x < N and 0 <= y < N:\n\t\t\treturn True\n\t\treturn False\n\n\tdef explore(self, target, pos, N, dis_x, dis_y, vis):\n\t\tq = deque()\n\t\tq.append(pos)\n\t\twhile len(q) != 0:\n\t\t\ta = q.popleft()\n\t\t\tfor i in range(8):\n\t\t\t\t(new_x, new_y) = (a[0] + dis_x[i], a[1] + dis_y[i])\n\t\t\t\tif self.check(N, new_x, new_y):\n\t\t\t\t\tif vis[new_x][new_y] == 0:\n\t\t\t\t\t\tvis[new_x][new_y] = vis[a[0]][a[1]] + 1\n\t\t\t\t\t\tq.append([new_x, new_y])\n\t\t\t\t\telif vis[new_x][new_y] > vis[a[0]][a[1]] + 1:\n\t\t\t\t\t\tvis[new_x][new_y] = vis[a[0]][a[1]] + 1\n\t\t\t\t\t\tq.append([new_x, new_y])\n\t\treturn vis[target[0]][target[1]]\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tdis_x = [1, -1, 1, -1, -2, -2, 2, 2]\n\t\tdis_y = [2, 2, -2, -2, 1, -1, -1, 1]\n\t\tvis = [[0 for i in range(N)] for j in range(N)]\n\t\tKnightPos = [KnightPos[0] - 1, KnightPos[1] - 1]\n\t\tTargetPos = [TargetPos[0] - 1, TargetPos[1] - 1]\n\t\tvis[KnightPos[0]][KnightPos[1]] = 0\n\t\ta = self.explore(TargetPos, KnightPos, N, dis_x, dis_y, vis)\n\t\treturn a\n", "class Cell:\n\n\tdef __init__(self, x=0, y=0, dist=0):\n\t\tself.x = x\n\t\tself.y = y\n\t\tself.dist = dist\n\nclass Solution:\n\n\tdef isInside(self, x, y, N):\n\t\tif x >= 1 and x <= N and (y >= 1) and (y <= N):\n\t\t\treturn True\n\t\treturn False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(tx, ty) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\t(x1, y1) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\tif x1 == tx and y1 == ty:\n\t\t\treturn 0\n\t\tvisited = [[0 for j in range(N)] for i in range(N)]\n\t\tqueue = []\n\t\tqueue.append([x1, y1])\n\t\tvisited[x1][y1] = 1\n\t\tstep = 0\n\t\tdirections = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]\n\t\twhile queue:\n\t\t\tstep += 1\n\t\t\tfor i in range(len(queue)):\n\t\t\t\t(X, Y) = queue.pop(0)\n\t\t\t\tfor (dx, dy) in directions:\n\t\t\t\t\tx = X + dx\n\t\t\t\t\ty = Y + dy\n\t\t\t\t\tif x == tx and y == ty:\n\t\t\t\t\t\treturn step\n\t\t\t\t\tif x >= 0 and x < N and (y >= 0) and (y < N) and (visited[x][y] == 0):\n\t\t\t\t\t\tvisited[x][y] = 1\n\t\t\t\t\t\tqueue.append([x, y])\n\t\treturn step if step > 0 else -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, kpos, tpos, n):\n\n\t\tdef bfs(i, j, vis, tpos, steps):\n\t\t\tq = []\n\t\t\tq.append((i, j, steps))\n\t\t\tvis.add((i, j))\n\t\t\twhile q:\n\t\t\t\t(r, c, st) = q.pop(0)\n\t\t\t\tif tpos[0] == r and tpos[1] == c:\n\t\t\t\t\treturn st\n\t\t\t\telse:\n\t\t\t\t\tfor (i, j) in [[-1, 2], [-1, -2], [1, 2], [1, -2], [-2, -1], [-2, 1], [2, -1], [2, 1]]:\n\t\t\t\t\t\t(nrow, ncol) = (r + i, j + c)\n\t\t\t\t\t\tif 1 <= nrow < n + 1 and 1 <= ncol < n + 1 and ((nrow, ncol) not in vis):\n\t\t\t\t\t\t\tq.append((nrow, ncol, st + 1))\n\t\t\t\t\t\t\tvis.add((nrow, ncol))\n\t\tvis = set()\n\t\tsteps = 0\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\tif kpos[0] == i and kpos[1] == j:\n\t\t\t\t\tans = bfs(i, j, vis, tpos, 0)\n\t\treturn ans\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tfrom collections import deque\n\t\tn = N\n\t\tvisited = [[False for i in range(n)] for j in range(n)]\n\t\tdr = [1, 2, 2, 1, -1, -2, -2, -1]\n\t\tdc = [-2, -1, 1, 2, 2, 1, -1, -2]\n\n\t\tdef bfs(row, col):\n\t\t\tq = deque()\n\t\t\tq.append((row, col, 0))\n\t\t\tvisited[row][col] = True\n\t\t\twhile q:\n\t\t\t\t(row, col, d) = q.popleft()\n\t\t\t\tif row == TargetPos[0] - 1 and col == TargetPos[1] - 1:\n\t\t\t\t\treturn d\n\t\t\t\tfor i in range(8):\n\t\t\t\t\tr = row + dr[i]\n\t\t\t\t\tc = col + dc[i]\n\t\t\t\t\tif r >= 0 and r < n and (c >= 0) and (c < n) and (not visited[r][c]):\n\t\t\t\t\t\tq.append((r, c, d + 1))\n\t\t\t\t\t\tvisited[r][c] = True\n\t\t\treturn -1\n\t\treturn bfs(KnightPos[0] - 1, KnightPos[1] - 1)\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, n):\n\t\tstart = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\ttarget = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\tmoves = [(2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2)]\n\t\tq = deque([(start, 0)])\n\t\tvisited = set([start])\n\t\twhile q:\n\t\t\t(cur, steps) = q.popleft()\n\t\t\tif cur == target:\n\t\t\t\treturn steps\n\t\t\tfor move in moves:\n\t\t\t\tnext_pos = (cur[0] + move[0], cur[1] + move[1])\n\t\t\t\tif next_pos[0] >= 0 and next_pos[0] < n and (next_pos[1] >= 0) and (next_pos[1] < n) and (next_pos not in visited):\n\t\t\t\t\tvisited.add(next_pos)\n\t\t\t\t\tq.append((next_pos, steps + 1))\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisited = [[False] * (N + 1) for _ in range(N + 1)]\n\t\tdire = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [-1, 2], [1, -2], [-1, -2]]\n\t\tqueue = []\n\t\trow = KnightPos[0]\n\t\tcol = KnightPos[1]\n\t\tqueue.append([row, col, 0])\n\t\tvisited[row][col] = True\n\n\t\tdef valid(tmp, n, m):\n\t\t\tif tmp[0] <= 0 or tmp[1] <= 0 or tmp[0] > n or (tmp[1] > m):\n\t\t\t\treturn False\n\t\t\telse:\n\t\t\t\treturn True\n\t\twhile len(queue) > 0:\n\t\t\ttmp = queue.pop(0)\n\t\t\tif tmp[0] == TargetPos[0] and tmp[1] == TargetPos[1]:\n\t\t\t\treturn tmp[2]\n\t\t\tfor e in dire:\n\t\t\t\tnex = [tmp[0] + e[0], tmp[1] + e[1], tmp[2] + 1]\n\t\t\t\tif not valid(nex, N, N):\n\t\t\t\t\tcontinue\n\t\t\t\tif not visited[nex[0]][nex[1]]:\n\t\t\t\t\tvisited[nex[0]][nex[1]] = True\n\t\t\t\t\tqueue.append(nex)\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = deque()\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\tTargetPos[0] -= 1\n\t\tTargetPos[1] -= 1\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tq.appendleft((KnightPos[0], KnightPos[1], 0))\n\t\tvis = set()\n\t\tvis.add((KnightPos[0], KnightPos[1]))\n\t\tdictio = {(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)}\n\t\tvis = set()\n\t\twhile q:\n\t\t\t(r, c, steps) = q.pop()\n\t\t\tfor (di, dj) in dictio:\n\t\t\t\t(n_i, n_j) = (r + di, c + dj)\n\t\t\t\tif n_i >= 0 and n_j >= 0 and (n_i < N) and (n_j < N) and ((n_i, n_j) not in vis):\n\t\t\t\t\tif [n_i, n_j] == TargetPos:\n\t\t\t\t\t\treturn steps + 1\n\t\t\t\t\tvis.add((n_i, n_j))\n\t\t\t\t\tq.appendleft((n_i, n_j, steps + 1))\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tlis = [[KnightPos[0], KnightPos[1], 0]]\n\t\tcount = 0\n\t\tpos = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n\t\tvis = {}\n\t\twhile lis:\n\t\t\t(r, c, ctr) = lis.pop(0)\n\t\t\tif r == TargetPos[0] and c == TargetPos[1]:\n\t\t\t\treturn ctr\n\t\t\tvis[r, c] = 1\n\t\t\tfor (i, j) in pos:\n\t\t\t\tR = r + i\n\t\t\t\tC = c + j\n\t\t\t\tif R >= 1 and R <= N and (C >= 1) and (C <= N) and ((R, C) not in vis):\n\t\t\t\t\tlis.append([R, C, ctr + 1])\n\t\t\t\t\tvis[R, C] = 1\n\t\treturn -1\n", "from queue import Queue\n\nclass Solution:\n\n\tdef isValid(self, i, j, N, visited):\n\t\tif i < 0 or j < 0 or i >= N or (j >= N) or (visited[i][j] == True):\n\t\t\treturn False\n\t\treturn True\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\tTargetPos[0] -= 1\n\t\tTargetPos[1] -= 1\n\t\tvisited = [[False for j in range(N)] for i in range(N)]\n\t\tq = Queue()\n\t\tq.put([KnightPos[0], KnightPos[1]])\n\t\tvisited[KnightPos[0]][KnightPos[1]] = True\n\t\tdx = [-2, -2, -1, 1, 2, 2, 1, -1]\n\t\tdy = [-1, 1, 2, 2, 1, -1, -2, -2]\n\t\tmoves = 0\n\t\twhile q.qsize() > 0:\n\t\t\tcurrsize = q.qsize()\n\t\t\tfor _ in range(currsize):\n\t\t\t\ttemp = q.get()\n\t\t\t\ti = temp[0]\n\t\t\t\tj = temp[1]\n\t\t\t\tif i == TargetPos[0] and j == TargetPos[1]:\n\t\t\t\t\treturn moves\n\t\t\t\tfor indx in range(8):\n\t\t\t\t\tx = dx[indx] + i\n\t\t\t\t\ty = dy[indx] + j\n\t\t\t\t\tif self.isValid(x, y, N, visited) == True:\n\t\t\t\t\t\tq.put([x, y])\n\t\t\t\t\t\tvisited[x][y] = True\n\t\t\tmoves += 1\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\tans = float('inf')\n\n\tdef minStepToReachTarget(self, src, des, N):\n\t\t(a, b) = src\n\t\tcnt = 0\n\t\tvisited = [[0 for _ in range(N)] for _ in range(N)]\n\t\treturn self.bfs(a - 1, b - 1, des, visited, N, cnt)\n\n\tdef bfs(self, a, b, des, visited, N, cnt):\n\t\tvisited[a][b] == 1\n\t\tqueue = deque()\n\t\tqueue.append((a, b, cnt))\n\t\twhile queue:\n\t\t\t(x, y, cnt) = queue.popleft()\n\t\t\tif x == des[0] - 1 and y == des[1] - 1:\n\t\t\t\treturn cnt\n\t\t\tdx = [-2, -1, 1, 2, -2, -1, 1, 2]\n\t\t\tdy = [-1, -2, -2, -1, 1, 2, 2, 1]\n\t\t\tfor j in range(8):\n\t\t\t\tnew_x = x + dx[j]\n\t\t\t\tnew_y = y + dy[j]\n\t\t\t\tif new_x >= 0 and new_y >= 0 and (new_x < N) and (new_y < N) and (visited[new_x][new_y] == 0):\n\t\t\t\t\tvisited[new_x][new_y] = 1\n\t\t\t\t\tqueue.append((new_x, new_y, cnt + 1))\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvis = [[0 for i in range(N)] for j in range(N)]\n\t\troww = [-2, -2, 2, 2, 1, -1, 1, -1]\n\t\tcoll = [-1, 1, -1, 1, -2, -2, 2, 2]\n\t\t(start_row, start_col) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\t(target_row, target_col) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\tvisited = [[False for _ in range(N)] for _ in range(N)]\n\t\tvisited[start_row][start_col] = True\n\t\tqueue = [(start_row, start_col, 0)]\n\t\twhile queue:\n\t\t\t(row, col, dist) = queue.pop(0)\n\t\t\tif row == target_row and col == target_col:\n\t\t\t\treturn dist\n\t\t\tfor i in range(8):\n\t\t\t\tnr = row + roww[i]\n\t\t\t\tnc = col + coll[i]\n\t\t\t\tif nr >= 0 and nc >= 0 and (nr < N) and (nc < N) and (vis[nr][nc] == 0):\n\t\t\t\t\tvis[nr][nc] = 1\n\t\t\t\t\tqueue.append((nr, nc, dist + 1))\n\t\treturn 0\n", "class Solution:\n\n\tdef isValid(self, row, col, n):\n\t\tif row >= 0 and row < n and (col >= 0) and (col < n):\n\t\t\treturn True\n\t\treturn False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tcount = 0\n\t\tdx = [1, 2, -1, 2, 1, -2, -1, -2]\n\t\tdy = [2, 1, -2, -1, -2, 1, 2, -1]\n\t\tqueue = []\n\t\tqueue.append([KnightPos[0] - 1, KnightPos[1] - 1, count])\n\t\tvisited = [[False for i in range(N)] for j in range(N)]\n\t\tvisited[KnightPos[0] - 1][KnightPos[1] - 1] = True\n\t\twhile len(queue):\n\t\t\tt = queue[0]\n\t\t\tqueue.pop(0)\n\t\t\tif t[0] == TargetPos[0] - 1 and t[1] == TargetPos[1] - 1:\n\t\t\t\treturn t[2]\n\t\t\tfor i in range(8):\n\t\t\t\tx = t[0] + dx[i]\n\t\t\t\ty = t[1] + dy[i]\n\t\t\t\tif self.isValid(x, y, N) and (not visited[x][y]):\n\t\t\t\t\tvisited[x][y] = True\n\t\t\t\t\tqueue.append([x, y, t[2] + 1])\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tdistance = []\n\t\tfor i in range(N):\n\t\t\tarr = []\n\t\t\tfor j in range(N):\n\t\t\t\tarr.append(0)\n\t\t\tdistance.append(arr)\n\t\tq = [(KnightPos[0] - 1, KnightPos[1] - 1)]\n\t\tvisited = set()\n\t\tmoves = [(2, 1), (-2, 1), (2, -1), (-2, -1), (-1, 2), (1, 2), (-1, -2), (1, -2)]\n\t\tsteps = 0\n\t\twhile q:\n\t\t\tpos = q.pop(0)\n\t\t\tvisited.add(pos)\n\t\t\tfor move in moves:\n\t\t\t\tx = pos[0] + move[0]\n\t\t\t\ty = pos[1] + move[1]\n\t\t\t\tif 0 <= x < N and 0 <= y < N and ((x, y) not in visited):\n\t\t\t\t\tvisited.add((x, y))\n\t\t\t\t\tq.append((x, y))\n\t\t\t\t\tdistance[x][y] = distance[pos[0]][pos[1]] + 1\n\t\t\t\t\tif x == TargetPos[0] - 1 and y == TargetPos[1] - 1:\n\t\t\t\t\t\treturn distance[x][y]\n\t\treturn -1\n", "import queue\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tminimum_steps = -1\n\t\tvisited = set((KnightPos[0], KnightPos[1]))\n\t\tmoves = [(-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1)]\n\t\tsource = (KnightPos[0], KnightPos[1], 0)\n\t\tq = queue.Queue()\n\t\tq.put(source)\n\t\twhile not q.empty():\n\t\t\t(j, i, step) = q.get()\n\t\t\tif [j, i] == TargetPos:\n\t\t\t\treturn step if minimum_steps == -1 else min(minimum_steps, step)\n\t\t\tfor move in moves:\n\t\t\t\tcolumn = j + move[0]\n\t\t\t\trow = i + move[1]\n\t\t\t\tif 1 <= row and row <= N and (1 <= column) and (column <= N):\n\t\t\t\t\tif (column, row) not in visited:\n\t\t\t\t\t\tvisited.add((column, row))\n\t\t\t\t\t\tq.put((column, row, step + 1))\n\t\treturn minimum_steps\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, targetPos, N):\n\t\tq = []\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\ttargetPos[0] -= 1\n\t\ttargetPos[1] -= 1\n\t\tsteps = 0\n\t\tdr = [1, 1, -1, -1, -2, -2, 2, 2]\n\t\tdc = [2, -2, 2, -2, 1, -1, 1, -1]\n\t\tq.append([0, KnightPos])\n\t\tvis = [[0] * N for i in range(N)]\n\t\tif KnightPos[0] == targetPos[0] and KnightPos[1] == targetPos[1]:\n\t\t\treturn 0\n\t\twhile q:\n\t\t\tnode = q.pop(0)\n\t\t\tsteps = node[0]\n\t\t\tr = node[1][0]\n\t\t\tc = node[1][1]\n\t\t\tfor i in range(len(dr)):\n\t\t\t\tnr = r + dr[i]\n\t\t\t\tnc = c + dc[i]\n\t\t\t\tif (nr >= 0 and nr < N) and (nc >= 0 and nc < N) and (vis[nr][nc] == 0):\n\t\t\t\t\tif nr == targetPos[0] and nc == targetPos[1]:\n\t\t\t\t\t\treturn steps + 1\n\t\t\t\t\tq.append([steps + 1, [nr, nc]])\n\t\t\t\t\tvis[nr][nc] = 1\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, s, d, n):\n\t\tq = deque([(s[0], s[1], 0)])\n\t\tneigh = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]\n\t\tseen = set()\n\t\tseen.add((s[0], s[1]))\n\t\twhile q:\n\t\t\t(i, j, steps) = q.popleft()\n\t\t\tif i == d[0] and j == d[1]:\n\t\t\t\treturn steps\n\t\t\tfor (x, y) in neigh:\n\t\t\t\tnx = i + x\n\t\t\t\tny = j + y\n\t\t\t\tif 0 < nx <= n and 0 < ny <= n and ((nx, ny) not in seen):\n\t\t\t\t\tseen.add((nx, ny))\n\t\t\t\t\tq.append((nx, ny, steps + 1))\n\t\treturn -1\n", "import sys\n\nclass Solution:\n\n\tdef isValid(self, i, j):\n\t\tif i > N or j > N or i <= 0 or (j <= 0):\n\t\t\treturn False\n\t\treturn True\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tdp = [[-1] * (N + 1) for i in range(N + 1)]\n\t\tdp[TargetPos[0]][TargetPos[1]] = 0\n\t\tq = []\n\t\tq.append((TargetPos[0], TargetPos[1]))\n\t\twhile len(q) > 0:\n\t\t\t(i, j) = q.pop(0)\n\t\t\tx = [2, 2, -2, -2, 1, 1, -1, -1]\n\t\t\ty = [1, -1, 1, -1, 2, -2, 2, -2]\n\t\t\tfor k in range(8):\n\t\t\t\t(ii, jj) = (i + x[k], j + y[k])\n\t\t\t\tif self.isValid(ii, jj) and dp[ii][jj] == -1:\n\t\t\t\t\tdp[ii][jj] = 1 + dp[i][j]\n\t\t\t\t\tq.append((ii, jj))\n\t\treturn dp[KnightPos[0]][KnightPos[1]]\n", "class Solution:\n\n\tdef valid(self, i, j, n):\n\t\treturn i >= 0 and j >= 0 and (i < n) and (j < n)\n\n\tdef minStepToReachTarget(self, k, t, N):\n\t\tx = [1, 1, -1, -1, 2, 2, -2, -2]\n\t\ty = [2, -2, 2, -2, 1, -1, 1, -1]\n\t\tminStep = [[10000001] * N for i in range(N)]\n\t\tqueue = []\n\t\tminStep[k[0] - 1][k[1] - 1] = 0\n\t\tqueue.append([k[0] - 1, k[1] - 1])\n\t\twhile len(queue) > 0:\n\t\t\tfront = queue.pop(0)\n\t\t\tfor i in range(8):\n\t\t\t\ta = x[i] + front[0]\n\t\t\t\tb = y[i] + front[1]\n\t\t\t\tif self.valid(a, b, N) and minStep[a][b] > minStep[front[0]][front[1]] + 1:\n\t\t\t\t\tminStep[a][b] = minStep[front[0]][front[1]] + 1\n\t\t\t\t\tqueue.append([a, b])\n\t\treturn minStep[t[0] - 1][t[1] - 1] if minStep[t[0] - 1][t[1] - 1] != 10000001 else -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef safe(self, row, col, n):\n\t\treturn True if row >= 1 and row <= n and (col >= 1) and (col <= n) else False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos[0] == TargetPos[0] and KnightPos[1] == TargetPos[1]:\n\t\t\treturn 0\n\t\tgrid = [[0 for i in range(N + 1)] for j in range(N + 1)]\n\t\trow_move = [-1, 1, -1, 1, 2, 2, -2, -2]\n\t\tcol_move = [2, 2, -2, -2, -1, 1, -1, 1]\n\t\tqueue = deque()\n\t\tqueue.append([KnightPos[1], KnightPos[0]])\n\t\tgrid[KnightPos[1]][KnightPos[0]] = 0\n\t\twhile queue:\n\t\t\tcell = queue.popleft()\n\t\t\tfor i in range(8):\n\t\t\t\trow = cell[0] + row_move[i]\n\t\t\t\tcol = cell[1] + col_move[i]\n\t\t\t\tif self.safe(row, col, N):\n\t\t\t\t\tparent_distance = grid[cell[0]][cell[1]]\n\t\t\t\t\tif grid[row][col] == 0:\n\t\t\t\t\t\tgrid[row][col] = 1 + parent_distance\n\t\t\t\t\t\tqueue.append([row, col])\n\t\t\t\t\telse:\n\t\t\t\t\t\tgrid[row][col] = min(grid[row][col], 1 + parent_distance)\n\t\tans = grid[TargetPos[1]][TargetPos[0]]\n\t\treturn ans if ans != 0 else -1\n", "from collections import deque\n\ndef getOptions(row, col):\n\treturn [[row - 1, col - 2], [row - 1, col + 2], [row + 1, col - 2], [row + 1, col + 2], [row - 2, col - 1], [row - 2, col - 1], [row - 2, col + 1], [row + 2, col - 1], [row + 2, col + 1]]\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tgrid = [[False for _ in range(N)] for _ in range(N)]\n\t\tqueue = deque([[KnightPos[0] - 1, KnightPos[1] - 1, 0]])\n\t\tgrid[KnightPos[0] - 1][KnightPos[1] - 1] = True\n\t\twhile queue:\n\t\t\t(row, col, move) = queue.popleft()\n\t\t\tfor (r, c) in getOptions(row, col):\n\t\t\t\tif r >= 0 and c >= 0 and (r < N) and (c < N) and (grid[r][c] == False):\n\t\t\t\t\tif r == TargetPos[0] - 1 and c == TargetPos[1] - 1:\n\t\t\t\t\t\treturn move + 1\n\t\t\t\t\tgrid[r][c] = True\n\t\t\t\t\tqueue.append([r, c, move + 1])\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tqueue = [([KnightPos[0] - 1, KnightPos[1] - 1], 0)]\n\t\tvisited = [[-1 for _ in range(N)] for _ in range(N)]\n\t\twhile queue:\n\t\t\tl = len(queue)\n\t\t\tx = queue.pop(0)\n\t\t\ta1 = x[0][0]\n\t\t\ta2 = x[0][1]\n\t\t\ta3 = x[1]\n\t\t\tif a1 == TargetPos[0] - 1 and a2 == TargetPos[1] - 1:\n\t\t\t\treturn a3\n\t\t\tif a1 + 1 < N and a2 + 2 < N and (visited[a1 + 1][a2 + 2] == -1):\n\t\t\t\tqueue.append(([a1 + 1, a2 + 2], a3 + 1))\n\t\t\t\tvisited[a1 + 1][a2 + 2] = 1\n\t\t\tif a1 - 1 >= 0 and a2 + 1 < N and (visited[a1 - 1][a2 + 1] == -1):\n\t\t\t\tqueue.append(([a1 - 1, a2 + 2], a3 + 1))\n\t\t\t\tvisited[a1 - 1][a2 + 1] = 1\n\t\t\tif a1 + 2 < N and a2 + 1 < N and (visited[a1 + 2][a2 + 1] == -1):\n\t\t\t\tqueue.append(([a1 + 2, a2 + 1], a3 + 1))\n\t\t\t\tvisited[a1 + 2][a2 + 1] = 1\n\t\t\tif a1 - 2 >= 0 and a2 + 1 < N and (visited[a1 - 2][a2 + 1] == -1):\n\t\t\t\tqueue.append(([a1 - 2, a2 + 1], a3 + 1))\n\t\t\t\tvisited[a1 - 2][a2 + 1] = 1\n\t\t\tif a1 + 1 < N and a2 - 2 >= 0 and (visited[a1 + 1][a2 - 2] == -1):\n\t\t\t\tqueue.append(([a1 + 1, a2 - 2], a3 + 1))\n\t\t\t\tvisited[a1 + 1][a2 - 2] = 1\n\t\t\tif a1 - 1 >= 0 and a2 - 2 >= 0 and (visited[a1 - 1][a2 - 2] == -1):\n\t\t\t\tqueue.append(([a1 - 1, a2 - 2], a3 + 1))\n\t\t\t\tvisited[a1 - 1][a2 - 2] = 1\n\t\t\tif a1 + 2 < N and a2 - 1 >= 0 and (visited[a1 + 2][a2 - 1] == -1):\n\t\t\t\tqueue.append(([a1 + 2, a2 - 1], a3 + 1))\n\t\t\t\tvisited[a1 + 2][a2 - 1] = 1\n\t\t\tif a1 - 2 >= 0 and a2 - 1 >= 0 and (visited[a1 - 2][a2 - 1] == -1):\n\t\t\t\tqueue.append(([a1 - 2, a2 - 1], a3 + 1))\n\t\t\t\tvisited[a1 - 2][a2 - 1] = 1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\trow = [-2, -2, -1, +1, +2, +2, -1, +1]\n\t\tcol = [+1, -1, +2, +2, +1, -1, -2, -2]\n\t\tAns = [9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999]\n\t\tvisited = {(KnightPos[0], KnightPos[1]): 1}\n\t\tqueue = [[KnightPos[0], KnightPos[1], 0]]\n\n\t\tdef checkBoundries(r, c):\n\t\t\tif r < 1 or r > N or c < 1 or (c > N):\n\t\t\t\treturn False\n\t\t\treturn True\n\n\t\tdef helper(x, y, count):\n\t\t\tif x == TargetPos[0] and y == TargetPos[1]:\n\t\t\t\tAns[0] = min(Ans[0], count)\n\t\t\t\treturn\n\t\t\tvisited[x, y] = 1\n\t\t\tfor i in range(8):\n\t\t\t\tr = x + row[i]\n\t\t\t\tc = y + col[i]\n\t\t\t\tif checkBoundries(r, c) and (r, c) not in visited:\n\t\t\t\t\tvisited[r, c] = 1\n\t\t\t\t\tqueue.append([r, c, count + 1])\n\t\twhile len(queue) > 0:\n\t\t\tbox = queue[0]\n\t\t\tqueue.pop(0)\n\t\t\thelper(box[0], box[1], box[2])\n\t\treturn Ans[0]\n", "from queue import Queue\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tdx = [1, 1, -1, -1, 2, 2, -2, -2]\n\t\tdy = [-2, 2, -2, 2, -1, 1, -1, 1]\n\n\t\tdef Adj(x, y):\n\t\t\tl = []\n\t\t\tfor k in range(8):\n\t\t\t\tif x + dx[k] >= 1 and y + dy[k] >= 1 and (y + dy[k] <= N) and (x + dx[k] <= N):\n\t\t\t\t\tl.append((x + dx[k], y + dy[k]))\n\t\t\treturn l\n\t\tq = Queue()\n\t\tlevel = {}\n\t\tvis = {}\n\t\tfor i in range(1, N + 1):\n\t\t\tfor j in range(1, N + 1):\n\t\t\t\tvis[i, j] = False\n\t\t\t\tlevel[i, j] = -1\n\t\ts = (KnightPos[0], KnightPos[1])\n\t\tq.put(s)\n\t\tvis[s] = True\n\t\tlevel[s] = 0\n\t\twhile not q.empty():\n\t\t\tu = q.get()\n\t\t\tx = u[0]\n\t\t\ty = u[1]\n\t\t\tif x == TargetPos[0] and y == TargetPos[1]:\n\t\t\t\treturn level[TargetPos[0], TargetPos[1]]\n\t\t\ta = Adj(x, y)\n\t\t\tfor v in a:\n\t\t\t\tif not vis[v]:\n\t\t\t\t\tvis[v] = True\n\t\t\t\t\tlevel[v] = level[u] + 1\n\t\t\t\t\tq.put(v)\n\t\treturn level[TargetPos[0], TargetPos[1]]\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisited = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tq = deque()\n\t\tq.append([KnightPos[0], KnightPos[1], 0])\n\t\tvisited[KnightPos[0]][KnightPos[1]] = True\n\t\tdi = [-2, -2, 2, 2, -1, 1, -1, 1]\n\t\tdj = [-1, 1, -1, 1, -2, -2, 2, 2]\n\t\twhile q:\n\t\t\t(i, j, d) = q.popleft()\n\t\t\tif i == TargetPos[0] and j == TargetPos[1]:\n\t\t\t\treturn d\n\t\t\tfor idx in range(8):\n\t\t\t\tdii = di[idx]\n\t\t\t\tdjj = dj[idx]\n\t\t\t\tif 1 <= i + dii <= N and 1 <= j + djj <= N and (not visited[i + dii][j + djj]):\n\t\t\t\t\tvisited[i + dii][j + djj] = True\n\t\t\t\t\tq.append([i + dii, j + djj, d + 1])\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef isValid(self, x, y, N):\n\t\treturn x >= 0 and x < N and (y >= 0) and (y < N)\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tdxy = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\tTargetPos[0] -= 1\n\t\tTargetPos[1] -= 1\n\t\tvis = [[False for i in range(N)] for j in range(N)]\n\t\tq = deque()\n\t\tq.append([KnightPos[0], KnightPos[1], 0])\n\t\tvis[KnightPos[0]][KnightPos[1]] = True\n\t\twhile len(q):\n\t\t\tcur = q.popleft()\n\t\t\tx = cur[0]\n\t\t\ty = cur[1]\n\t\t\tsteps = cur[2]\n\t\t\tif x == TargetPos[0] and y == TargetPos[1]:\n\t\t\t\treturn steps\n\t\t\tfor i in range(8):\n\t\t\t\tn_x = x + dxy[i][0]\n\t\t\t\tn_y = y + dxy[i][1]\n\t\t\t\tif self.isValid(n_x, n_y, N) and vis[n_x][n_y] == False:\n\t\t\t\t\tq.append([n_x, n_y, steps + 1])\n\t\t\t\t\tvis[n_x][n_y] = True\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, kp, tp, N):\n\t\tif kp == tp:\n\t\t\treturn 0\n\t\tg = [[-1 for i in range(N)] for j in range(N)]\n\t\tg[tp[0] - 1][tp[1] - 1] = 0\n\n\t\tdef check(a, b, n):\n\t\t\treturn a >= 0 and a < n and (b >= 0) and (b < n)\n\t\tmoves = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]\n\t\tq = [[tp[0] - 1, tp[1] - 1]]\n\t\tprev = 0\n\t\twhile q:\n\t\t\tnode = q.pop(0)\n\t\t\tprev = g[node[0]][node[1]]\n\t\t\tprev += 1\n\t\t\tfor move in moves:\n\t\t\t\t(a, b) = (node[0] + move[0], node[1] + move[1])\n\t\t\t\tif check(a, b, N) and g[a][b] < 0:\n\t\t\t\t\tif [a + 1, b + 1] == kp:\n\t\t\t\t\t\treturn prev\n\t\t\t\t\tg[a][b] = prev\n\t\t\t\t\tq.append([a, b])\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(start_row, start_col) = (KnightPos[0] - 1, KnightPos[1] - 1)\n\t\t(target_row, target_col) = (TargetPos[0] - 1, TargetPos[1] - 1)\n\t\tvisited = [[False for _ in range(N)] for _ in range(N)]\n\t\tvisited[start_row][start_col] = True\n\t\tqueue = [(start_row, start_col, 0)]\n\t\twhile queue:\n\t\t\t(row, col, dist) = queue.pop(0)\n\t\t\tif row == target_row and col == target_col:\n\t\t\t\treturn dist\n\t\t\tmoves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]\n\t\t\tfor move in moves:\n\t\t\t\t(new_row, new_col) = (row + move[0], col + move[1])\n\t\t\t\tif 0 <= new_row < N and 0 <= new_col < N and (not visited[new_row][new_col]):\n\t\t\t\t\tvisited[new_row][new_col] = True\n\t\t\t\t\tqueue.append((new_row, new_col, dist + 1))\n\t\treturn 0\n", "def isSafe(a, b, N):\n\tif a >= 0 and a < N and (b >= 0) and (b < N):\n\t\treturn True\n\treturn False\n\ndef dfs(sx, sy, visit, N, ex, ey, p):\n\tglobal steps\n\tif sx == ex and sy == ey:\n\t\tprint(p)\n\t\tsteps = min(steps, p)\n\t\treturn\n\tvisit[sx][sy] = 1\n\tx = [2, 2, 1, -1, -2, -2, -1, 1]\n\ty = [1, -1, 2, 2, 1, -1, -2, -2]\n\tfor i in range(8):\n\t\ta = sx + x[i]\n\t\tb = sy + y[i]\n\t\tif isSafe(a, b, N) and visit[a][b] == 0:\n\t\t\tdfs(a, b, visit, N, ex, ey, p + 1)\n\ndef bfs(sx, sy, visit, N, ex, ey, p):\n\tglobal steps\n\tif sx == ex and sy == ey:\n\t\tsteps = 0\n\t\treturn\n\tq = [[sx, sy, p]]\n\tvisit[sx][sy] = 1\n\tx = [2, 2, 1, -1, -2, -2, -1, 1]\n\ty = [1, -1, 2, 2, 1, -1, -2, -2]\n\twhile len(q) > 0:\n\t\t[tx, ty, tp] = q.pop(0)\n\t\tif tx == ex and ty == ey:\n\t\t\tsteps = tp\n\t\t\treturn\n\t\tfor i in range(8):\n\t\t\ta = tx + x[i]\n\t\t\tb = ty + y[i]\n\t\t\tif isSafe(a, b, N) and visit[a][b] == 0:\n\t\t\t\tq.append([a, b, tp + 1])\n\t\t\t\tvisit[a][b] = 1\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tglobal steps\n\t\tsteps = 100000000\n\t\tvisit = [[0 for i in range(N)] for i in range(N)]\n\t\tbfs(KnightPos[0] - 1, KnightPos[1] - 1, visit, N, TargetPos[0] - 1, TargetPos[1] - 1, 0)\n\t\treturn steps\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, n):\n\t\tq = []\n\t\tq.append([0, [KnightPos[0], KnightPos[1]]])\n\t\tvisited = [[0 for i in range(n + 1)] for j in range(n + 1)]\n\t\tvisited[KnightPos[0]][KnightPos[1]] = 1\n\t\tdelr = [-2, -1, 1, 2, -2, -1, 1, 2]\n\t\tdelc = [-1, -2, -2, -1, 1, 2, 2, 1]\n\t\twhile len(q) != 0:\n\t\t\t(steps, cell) = q.pop(0)\n\t\t\t(row, col) = cell\n\t\t\tif row == TargetPos[0] and col == TargetPos[1]:\n\t\t\t\treturn steps\n\t\t\tfor k in range(8):\n\t\t\t\tnrow = row + delr[k]\n\t\t\t\tncol = col + delc[k]\n\t\t\t\tif 1 <= nrow <= n and 1 <= ncol <= n and (visited[nrow][ncol] == 0):\n\t\t\t\t\tvisited[nrow][ncol] = 1\n\t\t\t\t\tq.append([steps + 1, [nrow, ncol]])\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, k, t, N):\n\t\tx = [2, 2, 1, -1, -2, -2, 1, -1]\n\t\ty = [-1, 1, 2, 2, -1, 1, -2, -2]\n\t\tif k[0] == t[0] and k[1] == t[1]:\n\t\t\treturn 0\n\t\tvis = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tq = []\n\t\tq.append((k[0], k[1]))\n\t\tcount = 0\n\t\twhile q:\n\t\t\tsz = len(q)\n\t\t\tcount += 1\n\t\t\tfor i in range(sz):\n\t\t\t\ttemp = q.pop(0)\n\t\t\t\t(dx, dy) = (temp[0], temp[1])\n\t\t\t\tfor d in range(8):\n\t\t\t\t\t(ni, nj) = (dx + x[d], dy + y[d])\n\t\t\t\t\tif ni > 0 and nj > 0 and (ni <= N) and (nj <= N) and (not vis[ni][nj]):\n\t\t\t\t\t\tif ni == t[0] and nj == t[1]:\n\t\t\t\t\t\t\treturn count\n\t\t\t\t\t\tq.append((ni, nj))\n\t\t\t\t\t\tvis[ni][nj] = 1\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, knightPos, t, N):\n\t\tq = [[knightPos[1] - 1, knightPos[0] - 1]]\n\t\tdist = [[float('inf') for i in range(N)] for i in range(N)]\n\t\tdist[knightPos[1] - 1][knightPos[0] - 1] = 0\n\t\twhile q:\n\t\t\t(x, y) = q.pop(0)\n\t\t\tfor (i, j) in ((x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), (x + 1, y + 2), (x - 1, y + 2)):\n\t\t\t\tif 0 <= i < N and 0 <= j < N:\n\t\t\t\t\tif dist[i][j] > dist[x][y] + 1:\n\t\t\t\t\t\tdist[i][j] = dist[x][y] + 1\n\t\t\t\t\t\tq.append([i, j])\n\t\treturn dist[t[1] - 1][t[0] - 1]\n", "class Solution:\n\n\tdef is_valid(self, i, j, n, visited):\n\t\tif i >= 0 and i < n and (j >= 0) and (j < n) and (visited[i][j] == 'false'):\n\t\t\treturn True\n\t\treturn False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tn = N\n\t\ttx = TargetPos[0] - 1\n\t\tty = TargetPos[1] - 1\n\t\tx1 = KnightPos[0] - 1\n\t\ty1 = KnightPos[1] - 1\n\t\tif x1 == tx and y1 == ty:\n\t\t\treturn 0\n\t\tvisited = [['false'] * n for i in range(n)]\n\t\tq = []\n\t\tq.append([x1, y1])\n\t\tvisited[x1][y1] = 'true'\n\t\tans = 0\n\t\twhile q:\n\t\t\tsize = len(q)\n\t\t\tans += 1\n\t\t\twhile size != 0:\n\t\t\t\t(xx, yy) = q.pop(0)\n\t\t\t\tax = [1, 1, -1, -1, 2, -2, 2, -2]\n\t\t\t\tay = [2, -2, 2, -2, 1, 1, -1, -1]\n\t\t\t\tfor i in range(8):\n\t\t\t\t\tnx = xx + ax[i]\n\t\t\t\t\tny = yy + ay[i]\n\t\t\t\t\tif nx == tx and ny == ty:\n\t\t\t\t\t\treturn ans\n\t\t\t\t\tif self.is_valid(nx, ny, n, visited):\n\t\t\t\t\t\tvisited[nx][ny] = 'true'\n\t\t\t\t\t\tq.append([nx, ny])\n\t\t\t\tsize -= 1\n\t\treturn ans\n", "from collections import deque\n\nclass Solution:\n\n\tdef isValid(self, row, col, n):\n\t\tif row <= n and row > 0 and (col <= n) and (col > 0):\n\t\t\treturn True\n\t\treturn False\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, n):\n\t\tvisited = [[0 for i in range(n + 1)] for j in range(n + 1)]\n\t\tq = deque()\n\t\tq.append([0, [KnightPos[0], KnightPos[1]]])\n\t\tvisited[KnightPos[0]][KnightPos[1]] = 1\n\t\tkr = [-2, -2, -1, -1, 2, 2, 1, 1]\n\t\tkc = [-1, 1, -2, 2, -1, 1, -2, 2]\n\t\twhile q:\n\t\t\ttop = q.popleft()\n\t\t\tsteps = top[0]\n\t\t\trow = top[1][0]\n\t\t\tcol = top[1][1]\n\t\t\tif row == TargetPos[0] and col == TargetPos[1]:\n\t\t\t\treturn steps\n\t\t\tfor i in range(8):\n\t\t\t\tjrow = row + kr[i]\n\t\t\t\tjcol = col + kc[i]\n\t\t\t\tif self.isValid(jrow, jcol, n) and visited[jrow][jcol] == 0:\n\t\t\t\t\tq.append([steps + 1, [jrow, jcol]])\n\t\t\t\t\tvisited[jrow][jcol] = 1\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(i, j) = KnightPos\n\t\ti -= 1\n\t\tj -= 1\n\t\t(x, y) = TargetPos\n\t\tx -= 1\n\t\ty -= 1\n\t\tvisited = set()\n\t\tvisited.add((i, j))\n\t\tq = deque()\n\t\tq.append([i, j, 0])\n\t\twhile q:\n\t\t\t(r, c, d) = q.popleft()\n\t\t\tif r == x and c == y:\n\t\t\t\treturn d\n\t\t\tfor (dx, dy) in [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]:\n\t\t\t\tnr = r + dx\n\t\t\t\tnc = c + dy\n\t\t\t\tif 0 <= nr < N and 0 <= nc < N and ((nr, nc) not in visited):\n\t\t\t\t\tvisited.add((nr, nc))\n\t\t\t\t\tq.append([nr, nc, d + 1])\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tq = [KnightPos]\n\t\tvisited = [[-1] * (N + 1) for i in range(N + 1)]\n\t\tvisited[KnightPos[0]][KnightPos[1]] = 0\n\t\twhile q:\n\t\t\tcurrent = q.pop(0)\n\t\t\t(row, col) = current\n\t\t\tcells = [(row - 1, col - 2), (row - 1, col + 2), (row - 2, col - 1), (row - 2, col + 1), (row + 1, col - 2), (row + 1, col + 2), (row + 2, col - 1), (row + 2, col + 1)]\n\t\t\tfor (nrow, ncol) in cells:\n\t\t\t\tif 1 <= nrow < N + 1 and 1 <= ncol < N + 1 and (visited[nrow][ncol] == -1):\n\t\t\t\t\tvisited[nrow][ncol] = visited[row][col] + 1\n\t\t\t\t\tq.append((nrow, ncol))\n\t\treturn visited[TargetPos[0]][TargetPos[1]]\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tKnightPos[0] -= 1\n\t\tKnightPos[1] -= 1\n\t\tTargetPos[0] -= 1\n\t\tTargetPos[1] -= 1\n\t\tboard = [[0] * N for _ in range(N)]\n\t\tqueue = deque()\n\t\tqueue.append(KnightPos + [0])\n\t\twhile queue:\n\t\t\t(i, j, count) = queue.popleft()\n\t\t\tif board[i][j]:\n\t\t\t\tcontinue\n\t\t\tboard[i][j] = 1\n\t\t\tif [i, j] == TargetPos:\n\t\t\t\treturn count\n\t\t\tif i > 1 and j > 0:\n\t\t\t\tqueue.append((i - 2, j - 1, count + 1))\n\t\t\tif i > 1 and j < N - 1:\n\t\t\t\tqueue.append((i - 2, j + 1, count + 1))\n\t\t\tif i > 0 and j > 1:\n\t\t\t\tqueue.append((i - 1, j - 2, count + 1))\n\t\t\tif i > 0 and j < N - 2:\n\t\t\t\tqueue.append((i - 1, j + 2, count + 1))\n\t\t\tif i < N - 1 and j > 1:\n\t\t\t\tqueue.append((i + 1, j - 2, count + 1))\n\t\t\tif i < N - 1 and j < N - 2:\n\t\t\t\tqueue.append((i + 1, j + 2, count + 1))\n\t\t\tif i < N - 2 and j > 0:\n\t\t\t\tqueue.append((i + 2, j - 1, count + 1))\n\t\t\tif i < N - 2 and j < N - 1:\n\t\t\t\tqueue.append((i + 2, j + 1, count + 1))\n\t\treturn -1\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(ix, iy) = KnightPos\n\t\tix -= 1\n\t\tiy -= 1\n\t\t(tx, ty) = TargetPos\n\t\ttx -= 1\n\t\tty -= 1\n\t\tvisited = set()\n\t\tx = deque()\n\t\tx.append((ix, iy))\n\t\tvisited.add((ix, iy))\n\t\tsteps = 0\n\t\twhile x:\n\t\t\tfor _ in range(len(x)):\n\t\t\t\t(i, j) = x.popleft()\n\t\t\t\tif i == tx and j == ty:\n\t\t\t\t\treturn steps\n\t\t\t\tfor (dx, dy) in [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]:\n\t\t\t\t\tnewi = i + dx\n\t\t\t\t\tnewj = j + dy\n\t\t\t\t\tif 0 <= newi < N and 0 <= newj < N and ((newi, newj) not in visited):\n\t\t\t\t\t\tvisited.add((newi, newj))\n\t\t\t\t\t\tx.append((newi, newj))\n\t\t\tsteps += 1\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tdp = [[0] * N for _ in range(N)]\n\t\tq = []\n\t\tq.append([KnightPos[0] - 1, KnightPos[1] - 1])\n\t\tdp[KnightPos[0] - 1][KnightPos[1] - 1] = 0\n\t\tx = [2, 1, -1, -2, -2, -1, 1, 2]\n\t\ty = [1, 2, 2, 1, -1, -2, -2, -1]\n\n\t\tdef Valid(i, j):\n\t\t\tif i < 0 or j < 0 or i > N - 1 or (j > N - 1) or (dp[i][j] != 0):\n\t\t\t\treturn False\n\t\t\treturn True\n\t\twhile len(q) != 0:\n\t\t\t(i, j) = q.pop(0)\n\t\t\tfor k in range(8):\n\t\t\t\tif Valid(i + x[k], j + y[k]):\n\t\t\t\t\tdp[i + x[k]][j + y[k]] = dp[i][j] + 1\n\t\t\t\t\tif i + x[k] == TargetPos[0] - 1 and j + y[k] == TargetPos[1] - 1:\n\t\t\t\t\t\treturn dp[i + x[k]][j + y[k]]\n\t\t\t\t\tq.append([i + x[k], j + y[k]])\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\n\t\tdef valid_next(i, j, N):\n\t\t\tdirections = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]\n\t\t\tret = []\n\t\t\tfor d in directions:\n\t\t\t\tx = i + d[0]\n\t\t\t\ty = j + d[1]\n\t\t\t\tif x > 0 and y > 0 and (x <= N) and (y <= N):\n\t\t\t\t\tret.append([x, y])\n\t\t\treturn ret\n\t\tque = deque()\n\t\tdepth = 0\n\t\tque.append(KnightPos)\n\t\tvisited = [[False] * (N + 1) for _ in range(N + 1)]\n\t\tvisited[KnightPos[0]][KnightPos[1]] = True\n\t\twhile que:\n\t\t\tn = len(que)\n\t\t\twhile n > 0:\n\t\t\t\tcur_pos = que.popleft()\n\t\t\t\tif cur_pos[0] == TargetPos[0] and cur_pos[1] == TargetPos[1]:\n\t\t\t\t\treturn depth\n\t\t\t\tall_next = valid_next(cur_pos[0], cur_pos[1], N)\n\t\t\t\tfor nxt in all_next:\n\t\t\t\t\tif not visited[nxt[0]][nxt[1]]:\n\t\t\t\t\t\tque.append(nxt)\n\t\t\t\t\t\tvisited[nxt[0]][nxt[1]] = True\n\t\t\t\tn -= 1\n\t\t\tdepth += 1\n\t\treturn -1 if len(que) == 0 else depth\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tdelrow = [1, 2, -2, -1, -1, -2, 1, 2]\n\t\tdelcol = [2, 1, 1, 2, -2, -1, -2, -1]\n\t\tqueue = [[KnightPos[0], KnightPos[1], 0]]\n\t\tvisited = [[0 for i in range(N + 1)] for j in range(N + 1)]\n\t\tvisited[KnightPos[0]][KnightPos[1]] = 1\n\t\twhile queue:\n\t\t\tr = queue[0][0]\n\t\t\tc = queue[0][1]\n\t\t\tsteps = queue[0][2]\n\t\t\tqueue.pop(0)\n\t\t\tif r == TargetPos[0] and c == TargetPos[1]:\n\t\t\t\treturn steps\n\t\t\tfor i in range(8):\n\t\t\t\tnr = r + delrow[i]\n\t\t\t\tnc = c + delcol[i]\n\t\t\t\tif nr >= 0 and nr < N + 1 and (nc >= 0) and (nc < N + 1) and (not visited[nr][nc]):\n\t\t\t\t\tvisited[nr][nc] = 1\n\t\t\t\t\tqueue.append([nr, nc, steps + 1])\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tR3 = [[0, 3, 2, 3], [3, 2, 1, 2], [2, 1, 4, 3], [3, 2, 3, 2]]\n\t\tx = abs(TargetPos[0] - KnightPos[0])\n\t\ty = abs(TargetPos[1] - KnightPos[1])\n\t\ta = 1\n\t\tb = 2\n\t\tresult = 0\n\t\twhile x > 3 or y > 3:\n\t\t\tif x > y:\n\t\t\t\tif x % 2 == 0 and x - y > 1:\n\t\t\t\t\ta = 2\n\t\t\t\t\tb = 1\n\t\t\t\telse:\n\t\t\t\t\ta = 1\n\t\t\t\t\tb = 2\n\t\t\telif y % 2 == 0 and y - x > 1:\n\t\t\t\ta = 1\n\t\t\t\tb = 2\n\t\t\telse:\n\t\t\t\ta = 2\n\t\t\t\tb = 1\n\t\t\tx = abs(x - a)\n\t\t\ty = abs(y - b)\n\t\t\tresult += 1\n\t\t\tif x < 4 and y < 4:\n\t\t\t\treturn result + R3[x][y]\n\t\treturn R3[x][y]\n", "from heapq import heappush, heappop\n\nclass Solution:\n\n\tdef bfs(self, node, pq, distance, row_poss, col_poss, n, target):\n\t\twhile len(pq):\n\t\t\t(steps, node) = pq[0]\n\t\t\tif node[0] == target[0] and node[1] == target[1]:\n\t\t\t\treturn steps\n\t\t\theappop(pq)\n\t\t\tfor k in range(8):\n\t\t\t\trow = node[0] + row_poss[k]\n\t\t\t\tcol = node[1] + col_poss[k]\n\t\t\t\tif row >= 1 and row <= n and (col >= 1) and (col <= n):\n\t\t\t\t\tif distance[node[0]][node[1]] + 1 < distance[row][col]:\n\t\t\t\t\t\tdistance[row][col] = distance[node[0]][node[1]] + 1\n\t\t\t\t\t\theappush(pq, (distance[row][col], (row, col)))\n\t\treturn -1\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tpq = []\n\t\tdistance = [[float('inf') for x in range(N + 1)] for x in range(N + 1)]\n\t\trow_poss = [-2, -2, -1, -1, 1, 1, 2, 2]\n\t\tcol_poss = [1, -1, 2, -2, 2, -2, 1, -1]\n\t\tdistance[KnightPos[0]][KnightPos[1]] = 0\n\t\theappush(pq, (0, (KnightPos[0], KnightPos[1])))\n\t\treturn self.bfs((KnightPos[0], KnightPos[1]), pq, distance, row_poss, col_poss, N, TargetPos)\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tkx = KnightPos[0] - 1\n\t\tky = KnightPos[1] - 1\n\t\ttx = TargetPos[0] - 1\n\t\tty = TargetPos[1] - 1\n\t\tif kx == tx and ky == ty:\n\t\t\treturn 0\n\t\tA = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tcl = [-2, -1, +1, +2, -2, -1, +1, +2]\n\t\trl = [-1, -2, -2, -1, +1, +2, +2, +1]\n\t\tA[ky][kx] = 0\n\t\tq = deque()\n\t\tq.append([ky, kx])\n\t\twhile len(q) > 0:\n\t\t\ttemp = q.popleft()\n\t\t\trow = temp[0]\n\t\t\tcol = temp[1]\n\t\t\tfor i in range(8):\n\t\t\t\tnewrow = row + rl[i]\n\t\t\t\tnewcol = col + cl[i]\n\t\t\t\tif newrow >= 0 and newrow < N and (newcol >= 0) and (newcol < N):\n\t\t\t\t\tif A[newrow][newcol] == False and newrow == ty and (newcol == tx):\n\t\t\t\t\t\treturn A[row][col] + 1\n\t\t\t\t\telif A[newrow][newcol] == False:\n\t\t\t\t\t\tq.append([newrow, newcol])\n\t\t\t\t\t\tA[newrow][newcol] = A[row][col] + 1\n\t\treturn -1\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tKnightPos = [KnightPos[0] - 1, KnightPos[1] - 1]\n\t\tTargetPos = [TargetPos[0] - 1, TargetPos[1] - 1]\n\t\tq = []\n\t\tq.append(KnightPos)\n\t\tdirr = [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-1, 2], [-2, 1]]\n\t\tdis = [[10 ** 8 for _ in range(N)] for _ in range(N)]\n\t\tdis[KnightPos[0]][KnightPos[1]] = 0\n\t\twhile q:\n\t\t\ttemp = q.pop(0)\n\t\t\tfor (i, j) in dirr:\n\t\t\t\tnewr = temp[0] + i\n\t\t\t\tnewc = temp[1] + j\n\t\t\t\tif newr < 0 or newc < 0 or newr >= N or (newc >= N) or (dis[newr][newc] <= dis[temp[0]][temp[1]] + 1):\n\t\t\t\t\tcontinue\n\t\t\t\tq.append([newr, newc])\n\t\t\t\tdis[newr][newc] = dis[temp[0]][temp[1]] + 1\n\t\tif dis[TargetPos[0]][TargetPos[1]] == 10 ** 8:\n\t\t\treturn -1\n\t\treturn dis[TargetPos[0]][TargetPos[1]]\n", "import sys\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tx_move = [1, 1, -1, -1, 2, 2, -2, -2]\n\t\ty_move = [2, -2, 2, -2, -1, 1, -1, 1]\n\t\tqueue = []\n\t\tvisited = [[False for _ in range(N + 1)] for _ in range(N + 1)]\n\t\tqueue.append([KnightPos[0], KnightPos[1], 0])\n\t\tvisited[KnightPos[0]][KnightPos[1]] = True\n\t\tmin_step_count = sys.maxsize\n\t\t(target_x, target_y) = (TargetPos[0], TargetPos[1])\n\t\twhile len(queue) != 0:\n\t\t\ttop = queue.pop(0)\n\t\t\t(X, Y, step_count) = (top[0], top[1], top[2])\n\t\t\tif [X, Y] == [target_x, target_y]:\n\t\t\t\tmin_step_count = min(min_step_count, step_count)\n\t\t\telse:\n\t\t\t\tfor (x, y) in zip(x_move, y_move):\n\t\t\t\t\t(X_new, Y_new) = (X + x, Y + y)\n\t\t\t\t\tif self.isValidPosition(X_new, Y_new, N) and (not visited[X_new][Y_new]):\n\t\t\t\t\t\tqueue.append([X_new, Y_new, step_count + 1])\n\t\t\t\t\t\tvisited[X_new][Y_new] = True\n\t\treturn min_step_count\n\n\tdef isValidPosition(self, X, Y, N):\n\t\treturn 1 <= X <= N and 1 <= Y <= N\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisited = [[False for j in range(N + 1)] for i in range(N + 1)]\n\t\tx1 = KnightPos[0]\n\t\ty1 = KnightPos[1]\n\t\tx2 = TargetPos[0]\n\t\ty2 = TargetPos[1]\n\t\tdire = [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]\n\t\tvisited[x1][y1] = True\n\t\tq = [(x1, y1, 0)]\n\t\twhile q:\n\t\t\t(i, j, dist) = q.pop(0)\n\t\t\tif i == x2 and j == y2:\n\t\t\t\treturn dist\n\t\t\tfor (dx, dy) in dire:\n\t\t\t\tnewR = i + dx\n\t\t\t\tnewC = j + dy\n\t\t\t\tif newR >= 1 and newR <= N and (newC >= 1) and (newC <= N) and (not visited[newR][newC]):\n\t\t\t\t\tvisited[newR][newC] = True\n\t\t\t\t\tq.append((newR, newC, dist + 1))\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tboard = [[0 for j in range(N)] for i in range(N)]\n\t\tx1 = KnightPos[0]\n\t\ty1 = KnightPos[1]\n\t\tx2 = TargetPos[0]\n\t\ty2 = TargetPos[1]\n\t\tq = [(x1 - 1, y1 - 1)]\n\t\twhile q:\n\t\t\t(i, j) = q.pop(0)\n\t\t\tif i + 1 >= 0 and i + 1 < N and (j + 2 >= 0) and (j + 2 < N) and (board[i + 1][j + 2] == 0):\n\t\t\t\tboard[i + 1][j + 2] += board[i][j] + 1\n\t\t\t\tq.append((i + 1, j + 2))\n\t\t\tif i - 1 >= 0 and i - 1 < N and (j + 2 >= 0) and (j + 2 < N) and (board[i - 1][j + 2] == 0):\n\t\t\t\tboard[i - 1][j + 2] += board[i][j] + 1\n\t\t\t\tq.append((i - 1, j + 2))\n\t\t\tif i - 2 >= 0 and i - 2 < N and (j + 1 >= 0) and (j + 1 < N) and (board[i - 2][j + 1] == 0):\n\t\t\t\tboard[i - 2][j + 1] += board[i][j] + 1\n\t\t\t\tq.append((i - 2, j + 1))\n\t\t\tif i + 2 >= 0 and i + 2 < N and (j + 1 >= 0) and (j + 1 < N) and (board[i + 2][j + 1] == 0):\n\t\t\t\tboard[i + 2][j + 1] += board[i][j] + 1\n\t\t\t\tq.append((i + 2, j + 1))\n\t\t\tif i - 1 >= 0 and i - 1 < N and (j - 2 >= 0) and (j - 2 < N) and (board[i - 1][j - 2] == 0):\n\t\t\t\tboard[i - 1][j - 2] += board[i][j] + 1\n\t\t\t\tq.append((i - 1, j - 2))\n\t\t\tif i + 1 >= 0 and i + 1 < N and (j - 2 >= 0) and (j - 2 < N) and (board[i + 1][j - 2] == 0):\n\t\t\t\tboard[i + 1][j - 2] += board[i][j] + 1\n\t\t\t\tq.append((i + 1, j - 2))\n\t\t\tif i - 2 >= 0 and i - 2 < N and (j - 1 >= 0) and (j - 1 < N) and (board[i - 2][j - 1] == 0):\n\t\t\t\tboard[i - 2][j - 1] += board[i][j] + 1\n\t\t\t\tq.append((i - 2, j - 1))\n\t\t\tif i + 2 >= 0 and i + 2 < N and (j - 1 >= 0) and (j - 1 < N) and (board[i + 2][j - 1] == 0):\n\t\t\t\tboard[i + 2][j - 1] += board[i][j] + 1\n\t\t\t\tq.append((i + 2, j - 1))\n\t\treturn board[x2 - 1][y2 - 1]\n", "from queue import Queue\n\ndef bfs(kp, tp, n):\n\t(nkp, ntp) = ((n - kp[1], kp[0] - 1), (n - tp[1], tp[0] - 1))\n\tstack = Queue()\n\tstack.put([nkp, 0])\n\tvisited = set()\n\twhile not stack.empty():\n\t\tpop = stack.get()\n\t\t(top, level) = (pop[0], pop[1])\n\t\tif top == ntp:\n\t\t\treturn level\n\t\tfor ngh in isValid(top[0], top[1], n):\n\t\t\tif ngh not in visited:\n\t\t\t\tvisited.add(ngh)\n\t\t\t\tstack.put([ngh, level + 1])\n\ndef isValid(i, j, n):\n\tneighs = []\n\tfor (a, b) in zip([-2, -2, -1, 1, 2, 2, 1, -1], [-1, 1, 2, 2, 1, -1, -2, -2]):\n\t\t(ta, tb) = (a + i, b + j)\n\t\tif ta >= 0 and ta < n and (tb >= 0) and (tb < n):\n\t\t\tneighs.append((ta, tb))\n\treturn neighs\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, kp, tp, n):\n\t\treturn bfs(kp, tp, n)\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisited = [[0 for _ in range(N)] for _ in range(N)]\n\t\tvisited[KnightPos[0] - 1][KnightPos[1] - 1] = 1\n\t\tvalidpos = [[2, -1], [2, 1], [1, -2], [1, 2], [-1, -2], [-1, 2], [-2, -1], [-2, 1]]\n\t\tq = [KnightPos, [-1]]\n\t\tans = 10 ** 10\n\t\tlevel = 0\n\t\twhile q:\n\t\t\ttemp = q.pop(0)\n\t\t\tif temp[0] == -1:\n\t\t\t\tlevel += 1\n\t\t\t\tif q:\n\t\t\t\t\tq.append([-1])\n\t\t\telif ans < level:\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tif temp == TargetPos and ans > level:\n\t\t\t\t\tans = level\n\t\t\t\tfor (x, y) in validpos:\n\t\t\t\t\tif 0 < temp[0] + x < N + 1 and 0 < temp[1] + y < N + 1 and (visited[temp[0] + x - 1][temp[1] + y - 1] == 0):\n\t\t\t\t\t\tvisited[temp[0] + x - 1][temp[1] + y - 1] = 1\n\t\t\t\t\t\tq.append([temp[0] + x, temp[1] + y])\n\t\tif ans == 10 ** 10:\n\t\t\treturn -1\n\t\treturn ans\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tif KnightPos == TargetPos:\n\t\t\treturn 0\n\t\tMAX = 1000000\n\t\tboard = []\n\t\tfor y in range(N):\n\t\t\tboard.append([])\n\t\t\tfor x in range(N):\n\t\t\t\tboard[y].append(MAX)\n\t\tmoves = []\n\t\tmoves.append([1, 2])\n\t\tmoves.append([-1, 2])\n\t\tmoves.append([1, -2])\n\t\tmoves.append([-1, -2])\n\t\tmoves.append([2, 1])\n\t\tmoves.append([-2, 1])\n\t\tmoves.append([2, -1])\n\t\tmoves.append([-2, -1])\n\t\tboard[N - KnightPos[1]][KnightPos[0] - 1] = 0\n\t\tboard[N - TargetPos[1]][TargetPos[0] - 1] = -1\n\t\tqueue = [[N - KnightPos[1], KnightPos[0] - 1]]\n\t\twhile len(queue) > 0:\n\t\t\titem = queue[0]\n\t\t\tdel queue[0]\n\t\t\ty = item[0]\n\t\t\tx = item[1]\n\t\t\tif board[y][x] != MAX and board[y][x] != -1:\n\t\t\t\tfor move in moves:\n\t\t\t\t\t_y = y + move[0]\n\t\t\t\t\t_x = x + move[1]\n\t\t\t\t\tif -1 < _y < N and -1 < _x < N:\n\t\t\t\t\t\t_new = board[y][x] + 1\n\t\t\t\t\t\tif board[_y][_x] == -1:\n\t\t\t\t\t\t\treturn _new\n\t\t\t\t\t\tif board[_y][_x] <= _new:\n\t\t\t\t\t\t\tcontinue\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tboard[_y][_x] = _new\n\t\t\t\t\t\t\tqueue.append([_y, _x])\n", "from collections import deque\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\tvisit = set()\n\t\tq = deque()\n\t\ti = KnightPos[0] - 1\n\t\tj = KnightPos[1] - 1\n\t\tfi = TargetPos[0] - 1\n\t\tfj = TargetPos[1] - 1\n\t\tif i == fi and j == fj:\n\t\t\treturn 0\n\t\tq.append([i, j])\n\t\tvisit.add((i, j))\n\t\tsteps = 0\n\t\tdirections = [[-2, -1], [-2, 1], [2, 1], [2, -1], [-1, -2], [-1, 2], [1, 2], [1, -2]]\n\n\t\tdef isValid(i, j):\n\t\t\tif i < 0 or j < 0 or i == N or (j == N) or ((i, j) in visit):\n\t\t\t\treturn False\n\t\t\treturn True\n\t\twhile q:\n\t\t\tl = len(q)\n\t\t\tfor i in range(l):\n\t\t\t\t(ci, cj) = q.popleft()\n\t\t\t\tif ci == fi and cj == fj:\n\t\t\t\t\treturn steps\n\t\t\t\tfor (dr, dc) in directions:\n\t\t\t\t\tr = ci + dr\n\t\t\t\t\tc = cj + dc\n\t\t\t\t\tif r == fi and c == fj:\n\t\t\t\t\t\treturn steps + 1\n\t\t\t\t\tif isValid(r, c):\n\t\t\t\t\t\tvisit.add((r, c))\n\t\t\t\t\t\tq.append([r, c])\n\t\t\tsteps += 1\n\t\treturn -1\n", "def isValid(i, j, n, vis):\n\tif i >= 0 and j >= 0 and (i < n) and (j < n) and (vis[i][j] == 0):\n\t\treturn True\n\treturn False\n\nclass Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, n):\n\t\ttx = TargetPos[0] - 1\n\t\tty = TargetPos[1] - 1\n\t\tx1 = KnightPos[0] - 1\n\t\ty1 = KnightPos[1] - 1\n\t\tq = []\n\t\tif x1 == tx and y1 == ty:\n\t\t\treturn 0\n\t\tq.append([x1, y1])\n\t\tvis = [[0 for i in range(n)] for j in range(n)]\n\t\tvis[x1][y1] = 1\n\t\tans = 0\n\t\twhile len(q) != 0:\n\t\t\tsize = len(q)\n\t\t\tans += 1\n\t\t\twhile size != 0:\n\t\t\t\tele = q.pop(0)\n\t\t\t\txx = ele[0]\n\t\t\t\tyy = ele[1]\n\t\t\t\tax = [1, 1, -1, -1, 2, -2, 2, -2]\n\t\t\t\tay = [2, -2, 2, -2, 1, 1, -1, -1]\n\t\t\t\tfor i in range(8):\n\t\t\t\t\tnx = xx + ax[i]\n\t\t\t\t\tny = yy + ay[i]\n\t\t\t\t\tif nx == tx and ty == ny:\n\t\t\t\t\t\treturn ans\n\t\t\t\t\tif isValid(nx, ny, n, vis):\n\t\t\t\t\t\tvis[nx][ny] = 1\n\t\t\t\t\t\tq.append([nx, ny])\n\t\t\t\tsize -= 1\n\t\treturn ans\n", "class Solution:\n\n\tdef minStepToReachTarget(self, KnightPos, TargetPos, N):\n\t\t(ik, jk) = KnightPos = tuple(KnightPos)\n\t\tTargetPos = tuple(TargetPos)\n\t\tdist = [[False for i in range(N + 1)] for j in range(N + 1)]\n\t\tdist[ik][jk] = 0\n\t\tp_q = [KnightPos]\n\t\twhile len(p_q) > 0:\n\t\t\t(i, j) = point = p_q.pop(0)\n\t\t\tdist_i = dist[i][j]\n\t\t\tif TargetPos[0] == i and TargetPos[1] == j:\n\t\t\t\treturn dist[i][j]\n\t\t\tself.add_next_valid_points(point, dist, p_q, N)\n\t\treturn -1\n\n\tdef add_next_valid_points(self, crnt_point, dist, p_q, N):\n\t\t(i, j) = crnt_point\n\t\tpoints = [(i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2)]\n\t\tcrnt_dist = dist[i][j]\n\t\tfor point in points:\n\t\t\t(ip, jp) = point\n\t\t\tif self.is_valid_point(point, N) and (not dist[ip][jp]):\n\t\t\t\tp_q.append(point)\n\t\t\t\tdist[ip][jp] = crnt_dist + 1\n\n\tdef is_valid_point(self, point, N):\n\t\tif point[0] < 1 or point[0] > N:\n\t\t\treturn False\n\t\tif point[1] < 1 or point[1] > N:\n\t\t\treturn False\n\t\treturn True\n"]

starter_code:
class Solution:

	#Function to find out minimum steps Knight needs to reach target position.

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		#Code here

difficulty: MEDIUM

raw_tags: ['Algorithms', 'BFS', 'Queue', 'Data Structures', 'Graph']

source: geekforgeeks

tags: ['Data structures', 'Graph algorithms', 'Graph traversal']

skill_types: ['Data structures']

raw_problem:
Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.

Note:
The initial and the target position coordinates of Knight have been given according to 1-base indexing.

Example 1:

Input:
N=6
knightPos[ ] = {4, 5}
targetPos[ ] = {1, 1}
Output:
3
Explanation:

Knight takes 3 step to reach from
(4, 5) to (1, 1):
(4, 5) -> (5, 3) -> (3, 2) -> (1, 1).

Your Task:
You don't need to read input or print anything. Your task is to complete the function minStepToReachTarget() which takes the initial position of Knight (KnightPos), the target position of Knight (TargetPos), and the size of the chessboard (N) as input parameters and returns the minimum number of steps required by the knight to reach from its current position to the given target position or return -1 if its not possible.

Expected Time Complexity: O(N2).
Expected Auxiliary Space: O(N2).

Constraints:
1 <= N <= 1000
1 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N

question:
Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.
Note:The initial and the target position coordinates of Knight have been given according to 1-base indexing.

Example 1:
Input:
N=6
knightPos[ ] = {4, 5}
targetPos[ ] = {1, 1}
Output:
3
Explanation:
![image](1.png)
Knight takes 3 step to reach from
(4, 5) to (1, 1):
(4, 5) -> (5, 3) -> (3, 2) -> (1, 1).

Your Task:You don't need to read input or print anything. Your task is to complete the function minStepToReachTarget() which takes the initial position of Knight (KnightPos), the target position of Knight (TargetPos), and the size of the chessboard (N) as input parameters and returns the minimum number of steps required by the knight to reach from its current position to the given target position or return -1 if its not possible.

Expected Time Complexity: O(N^{2}).Expected Auxiliary Space: O(N^{2}).

Constraints:1 <= N <= 10001 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N

data_split: test