-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdfs.py
78 lines (68 loc) · 3.11 KB
/
dfs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import queue as qe
import state as maf
from collections import deque
import numpy as np
def dfs(initial_state):
stack = [initial_state]
visited = {initial_state.get_hash(): True}
while stack:
current_state = stack.pop()
if current_state.you_loser():
return [], [], []
if current_state.you_win():
win_path = []
path = []
while current_state:
path.append(current_state.parent)
win_path.append(current_state)
current_state = current_state.parent1
path.reverse()
len_visited = len(visited)
return win_path[::-1], path, len_visited
for move in current_state.all_next_state_move():
move_hash = move.get_hash()
if move_hash not in visited:
visited[move_hash] = True
stack.append(move)
move.parent1 = current_state
return [], [], []
# initial_state = maf. map_state(11)
# initial_state.parent = "root"
# initial_state.printer(1, 1, "black", "⬛️", False, False)
# initial_state.printer(1, 6, "black", "⬛️", False, False)
# initial_state.printer(1, 5, "black", "⬛️", False, False)
# initial_state.printer(1, 7, "black", "⬛️", False, False)
# initial_state.printer(2, 5, "black", "⬛️", False, False)
# initial_state.printer(1, 8, "black", "⬛️", False, False)
# initial_state.printer(1, 9, "black", "⬛️", False, False)
# initial_state.printer(2, 6, "black", "⬛️", False, False)
# initial_state.printer(2, 9, "black", "⬛️", False, False)
# initial_state.printer(3, 9, "black", "⬛️", False, False)
# initial_state.printer(5, 9, "black", "⬛️", False, False)
# initial_state.printer(6, 1, "black", "⬛️", False, False)
# initial_state.printer(6, 4, "black", "⬛️", False, False)
# initial_state.printer(6, 5, "black", "⬛️", False, False)
# initial_state.printer(6, 6, "black", "⬛️", False, False)
# initial_state.printer(6, 7, "black", "⬛️", False, False)
# initial_state.printer(6, 8, "black", "⬛️", False, False)
# initial_state.printer(6, 9, "black", "⬛️", False, False)
# initial_state.printer(7, 1, "black", "⬛️", False, False)
# initial_state.printer(7, 2, "black", "⬛️", False, False)
# initial_state.printer(7, 3, "black", "⬛️", False, False)
# initial_state.printer(7, 4, "black", "⬛️", False, False)
# initial_state.printer(4, 4, "black", "⬛️", False, False)
# initial_state.printer(4, 6, "black", "⬛️", False, False)
# initial_state.printer(4, 5, "black", "⬛️", False, False)
# # initial_state.printer(4, 9, "red", "🔴", True, False)
# # initial_state.printer(1, 2, "red", "🟥", False, False)
# initial_state.printer(2, 7, "blue", "🔵", True, False)
# initial_state.printer(4, 2, "blue", "🟦", False, False)
# initial_state.printer(4, 3, "red", "🟥", False, False)
# initial_state.printer(1, 3, "red", "🔴", True, False)
# initial_state.print_map()
# state, path, len_visited = dfs(initial_state)
# print("len_visited:", len_visited)
# print(" len path :", len(path))
# print(path)
# for item in state:
# item.print_map()