AOJ 0503 Cup with python
続きです。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503
問題概要
大きさが小さい順にカップが積まれている皿が 3 つあり、隣の皿に、うつしていって(カップの大きさが小さい→大きいの動かし方はだめ)、最も左か最も右に移す最小手順数を出力する。
考えた解法
BFSでシミュレートする。それぞれの皿の状況をまるまるqueueに追加する。 カップを変える時、a→bに動かした時、次は、b→aには動かさない、また、動かした後、a→bに動かすことはできない。これで、queueに入れる状態の数は少なくなる。
遅いけど(3.2s)コードがめちゃめちゃスッキリしてる。
from collections import deque def main(): while True: n, m = [int(i) for i in input().split()] if n == 0 and m == 0: return _, *a = [int(i) for i in input().split()] _, *b = [int(i) for i in input().split()] _, *c = [int(i) for i in input().split()] a.insert(0, 0) b.insert(0, 0) c.insert(0, 0) q = deque() q.appendleft([a, b, c, 0, -1]) tmp = [i for i in range(0, n+1)] while q: # d はカウンタ a, b, c, d, t = q.pop() """ print(a) print(b) print(c) print('=======') """ # 終了 if d > m: print(-1) break if a == tmp or c == tmp: print(d) break # a から b if a[-1] > b[-1] and t != 1: q.appendleft([a[:-1], b+[a[-1]], c[:], d+1, 0]) # b から a if b[-1] > a[-1] and t != 0: q.appendleft([a+[b[-1]], b[:-1], c[:], d+1, 1]) # b から c if b[-1] > c[-1] and t != 3: q.appendleft([a[:], b[:-1], c+[b[-1]], d+1, 2]) # c から b if c[-1] > b[-1] and t!= 2: q.appendleft([a[:], b+[c[-1]], c[:-1], d+1, 3]) if __name__ == '__main__': main()