Baekjoon #7562 Knight
Conditions
- 3 input values:
- board length l
- source (x,y)
- destination (x, y)
- Count how many moves needs to go to the destination.
Strategy
- Visit all board using bfs.
- In each turn, the knight can visit 8 directions.
- Knight can move only on the board, not the outside. -> Need to check the coordinate.
1import sys
2r = sys.stdin.readline
3
4
5def bfs(src: tuple, dst: tuple, l: int, visited: list, count: list) -> None:
6 from collections import deque
7 q = deque()
8 q.appendleft(src)
9
10 while q:
11 this = q.pop()
12 this_x, this_y = this
13 if this == dst:
14 break
15 visited[this_x][this_y] = 1
16
17 next_list = [(this_x-2, this_y+1), (this_x-1, this_y+2), (this_x+1, this_y+2), (this_x+2, this_y+1),
18 (this_x-2, this_y-1), (this_x-1, this_y-2), (this_x+1, this_y-2), (this_x+2, this_y-1)]
19 for each in next_list:
20 each_x, each_y = each
21 if 0 <= each_x < l and 0 <= each_y < l and visited[each_x][each_y] == 0:
22 count[each_x][each_y] = count[this_x][this_y] + 1
23 visited[each_x][each_y] = 1
24 q.appendleft(each)
25
26
27if __name__ == "__main__":
28 test = int(r())
29 l_list = []
30 src_list = []
31 dst_list = []
32
33 for i in range(test):
34 l_list.append(int(r()))
35 src_list.append(tuple(map(int, r().split())))
36 dst_list.append(tuple(map(int, r().split())))
37
38 for i in range(test):
39 l = l_list[i]
40 src = src_list[i]
41 dst = dst_list[i]
42
43 if src == dst:
44 print(0)
45 continue
46
47 visited = [[0 for _ in range(l)] for _ in range(l)]
48 count = [[0 for _ in range(l)] for _ in range(l)]
49
50 bfs(src, dst, l, visited, count)
51
52 print(count[dst[0]][dst[1]])
Remember
I wrote like below, at first.
1if each_x not in range(l) or each_y not in range(l):
But this made more overheads, because 2 range() method made a sequence, iterable object, every turn and in keyword took $$O(n)$$ time to find.
1if 0 <= each_x < l and 0 <= each_y < l and visited[each_x][each_y] == 0:
This change has 4 comparison, but it’s more faster than find in range(l) for twice.
Comments