perogram

8パズルの最短での解き方 How to solve 8 Puzzle

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B

Submission

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3610307#1

参考

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2084544#1

解法

  • 各盤面を状態としたbfs

ポイント

  • map<Puzzle, bool>で「その状態はすでに来たことがあるか?」を管理
  • mapにPuzzleを入れるために、Puzzleには比較オペレータ "<" を定義しておく

かかった時間

  • 1sec制限
  • CPU: 00:33 sec

15パズルだと工夫が必要?

15 Puzzle 15パズルも解いたよ!

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造