|
- here, there = 0, 1
- s = [here] * 8 # hunter, wolf, female, child1, child2, older, child3, child4
- state = []
- for i in range(256):
- k = i
- for j in range(8):
- s[7 - j] = k % 2
- k >>= 1
- # 狼吃人
- if s[0] != s[1] and (s[1] == s[2] or s[1] == s[3] or s[1] == s[4] or s[1] == s[5] or s[1] == s[6] or s[1] == s[7]):
- continue
- # 女人老人不在一起,孩子被打
- if s[2] != s[5] and (s[2] == s[6] or s[2] == s[7] or s[5] == s[3] or s[5] == s[4]):
- continue
- state.append((tuple(s), i))
- action = {}
- for i in range(len(state)):
- for j in range(i + 1, len(state)):
- if state[i][0][0] != state[j][0][0] or state[i][0][2] != state[j][0][2]:
- if bin(state[i][1] ^ state[j][1]).count('1') <= 2 and bin(state[i][1]).count('1') != bin(state[j][1]).count('1'):
- action[state[i][0]] = action.get(state[i][0], []) + [state[j][0]]
- action[state[j][0]] = action.get(state[j][0], []) + [state[i][0]]
- path = []
- def find(state):
- if state == (1, 1, 1, 1, 1, 1, 1, 1):
- return True
- for i in action[state]:
- if i in path:
- continue
- path.append(i)
- if find(i):
- return True
- path.pop()
- return False
- find(tuple([here] * 8)) # False找不到
复制代码 状态转移的图搜索算法, 反正就是找不到路径,过不去
|
|