Scanning UPC Barcodes (UVa Live Archive North America - Greater New York - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4880

問題

一部が読み取れず、左右も分からないバーコードの入力を与えるので、存在し得る数値の列を答えよ。

解法

メモ化dfsで解く。ただし、9個解を見つけた場合は探索を打ち切る。