Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def check(matr, i, j):
- if i < 0 or j < 0 or j >= len(matr) or i >= len(matr) or matr[i][j] == 1:
- return False
- return True
- def bfs(matr, sX, sY, fX, fY):
- dy = [2, 2, 1, 1, -1, -1, -2, -2]
- dx = [1, -1, 2, -2, 2, -2, 1, -1]
- currx = sX
- curry = sY
- queue = []
- for i in range(len(dy)):
- newx = currx + dx[i]
- newy = curry + dy[i]
- if (check(matr, newx, newy)):
- matr[newx][newy] = 1
- queue.append(newx)
- queue.append(newy)
- queue.append(1)
- while len(queue) > 0:
- currx = queue[0]
- curry = queue[1]
- cnt = queue[2]
- if currx == fX and curry == fY:
- return cnt
- queue.pop(0)
- queue.pop(0)
- queue.pop(0)
- for i in range(len(dy)):
- newx = currx + dx[i]
- newy = curry + dy[i]
- if (check(matr, newx, newy)):
- matr[newx][newy] = 1
- queue.append(newx)
- queue.append(newy)
- queue.append(cnt + 1)
- n = int(input())
- matr = [[0 for x in range(n)] for i in range(n)] #???
- sX, sY = map(int, input().split())
- sX -= 1
- sY -= 1
- fX, fY = map(int, input().split())
- fX -= 1
- fY -= 1
- if sX == fX and sY == fY:
- print(0)
- else:
- print(bfs(matr, sX, sY, fX, fY))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement