• API
• FAQ
• Tools
• Archive
daily pastebin goal
36%
SHARE
TWEET

Untitled

a guest Oct 12th, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def check(matr, i, j):
2.     if i < 0 or j < 0 or j >= len(matr) or i >= len(matr) or matr[i][j] == 1:
3.         return False
4.     return True
5.
6. def bfs(matr, sX, sY, fX, fY):
7.     dy = [2, 2, 1, 1, -1, -1, -2, -2]
8.     dx = [1, -1, 2, -2, 2, -2, 1, -1]
9.     currx = sX
10.     curry = sY
11.     queue = []
12.     for i in range(len(dy)):
13.         newx = currx + dx[i]
14.         newy = curry + dy[i]
15.         if (check(matr, newx, newy)):
16.             matr[newx][newy] = 1
17.             queue.append(newx)
18.             queue.append(newy)
19.             queue.append(1)
20.     while len(queue) > 0:
21.         currx = queue[0]
22.         curry = queue[1]
23.         cnt = queue[2]
24.         if currx == fX and curry == fY:
25.             return cnt
26.         queue.pop(0)
27.         queue.pop(0)
28.         queue.pop(0)
29.         for i in range(len(dy)):
30.             newx = currx + dx[i]
31.             newy = curry + dy[i]
32.             if (check(matr, newx, newy)):
33.                 matr[newx][newy] = 1
34.                 queue.append(newx)
35.                 queue.append(newy)
36.                 queue.append(cnt + 1)
37.
38. n = int(input())
39. matr = [[0 for x in range(n)] for i in range(n)] #???
40. sX, sY = map(int, input().split())
41. sX -= 1
42. sY -= 1
43. fX, fY = map(int, input().split())
44. fX -= 1
45. fY -= 1
46. if sX == fX and sY == fY:
47.     print(0)
48. else:
49.     print(bfs(matr, sX, sY, fX, fY))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top