Skip to content

Instantly share code, notes, and snippets.

@snuke

snuke/input.txt

Last active August 6, 2017 10:02
Show Gist options
  • Save snuke/d99742b4c6023b06c7143d9274aa3a74 to your computer and use it in GitHub Desktop.
Save snuke/d99742b4c6023b06c7143d9274aa3a74 to your computer and use it in GitHub Desktop.
Download ZIP
UTPC2017 (puzzle) 計算迷路２
Raw
readme.md

最大は 63 で、なんと唯一解でした。

graphillionというライブラリを使って厳密解を求めてみました。

このライブラリでは、パスや木のようなグラフを列挙することができます。
要は、数え上げお姉さんを救うためのライブラリです（違）

このライブラリには、辺に重みをつけるとパスを辺の重みの大きい順に列挙できる機能もあり、それを使いました。
元の問題では頂点に重みがついているのですが、辺の重みを端点の重みの平均とすることで、辺に重みがついている問題に変換できます。

このサイズだと、最適解は１秒ほどで計算できました。
最小も求めてみたところ -61 で、12通りありました。（右辺と下辺の通り方が2通りずつ、上辺が3通り）

Raw
input.txt
9
9 -9 8 -7 2 -5 3 -4 9
-5 3 -1 6 -5 5 -2 6 -8
5 -4 3 -6 4 -9 1 -4 7
-9 1 -1 4 -8 7 -7 5 -1
4 -7 2 0 20 0 4 -2 3
-4 5 -5 7 -9 6 -3 6 -5
8 -6 3 -6 1 -8 5 -1 3
-3 1 -8 9 -6 4 -5 6 -4
2 -1 4 -3 6 -7 2 -2 4　　　　　　　　　　　　　　　　　　
Raw
max.txt
score : 63
length: 48
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9===-9=== 8 | -7 | 2 | -5 | 3 | -4=== 9 |
| || | | || | | | | | || | || |
+-||-+----+-||-+----+----+----+----+-||-+-||-+
| || | | || | | | | | || | || |
| -5 | 3 | -1=== 6===-5=== 5===-2=== 6 | -8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5===-4=== 3 | -6 | 4 | -9 | 1 | -4 | 7 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -9 | 1 | -1=== 4===-8 | 7 | -7 | 5===-1 |
| | | | | || | | | || | |
+----+----+----+----+-||-+----+----+-||-+----+
| | | | | || | | | || | |
| 4 | -7 | 2 | S | 20=== G | 4 | -2 | 3 |
| | | | || | | | | || | |
+----+----+----+-||-+----+----+----+-||-+----+
| | | | || | | | | || | |
| -4=== 5===-5=== 7 | -9 | 6 | -3=== 6 | -5 |
| || | | | | | | || | | |
+-||-+----+----+----+----+----+-||-+----+----+
| || | | | | | | || | | |
| 8 | -6 | 3 | -6 | 1 | -8 | 5===-1=== 3 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| -3 | 1 | -8 | 9===-6=== 4===-5=== 6 | -4 |
| || | | | || | | | | || | || |
+-||-+----+----+-||-+----+----+----+-||-+-||-+
| || | | | || | | | | || | || |
| 2===-1=== 4===-3 | 6 | -7 | 2 | -2=== 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
Raw
min.txt
-61
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2 | -5=== 3===-4 | 9 |
| | || | | | || | || | | || | |
+----+-||-+----+----+-||-+-||-+----+-||-+----+
| | || | | | || | || | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2 | -5=== 3===-4 | 9 |
| | || | | | || | || | | || | |
+----+-||-+----+----+-||-+-||-+----+-||-+----+
| | || | | | || | || | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2 | -5=== 3===-4 | 9 |
| | || | | | || | || | | || | |
+----+-||-+----+----+-||-+-||-+----+-||-+----+
| | || | | | || | || | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2 | -5=== 3===-4 | 9 |
| | || | | | || | || | | || | |
+----+-||-+----+----+-||-+-||-+----+-||-+----+
| | || | | | || | || | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5 | 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5 | 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5 | 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5 | 5 | -2 | 6===-8 |
| || | | | | | | | | || |
+-||-+----+----+----+----+----+----+----+-||-+
| || | | | | | | | | || |
| 5 | -4=== 3===-6 | 4===-9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | || | || | | | || |
+-||-+----+----+----+-||-+-||-+----+----+-||-+
| || | | | | || | || | | | || |
| 5 | -4=== 3===-6 | 4 | -9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | || | || | | | || |
+-||-+----+----+----+-||-+-||-+----+----+-||-+
| || | | | | || | || | | | || |
| 5 | -4=== 3===-6 | 4 | -9=== 1 | -4 | 7 |
| || | || | | || | || | | || | | || |
+-||-+-||-+----+-||-+-||-+----+-||-+----+-||-+
| || | || | | || | || | | || | | || |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | | || |
+-||-+-||-+----+----+----+----+-||-+----+-||-+
| || | || | | | | | || | | || |
| 4===-7 | 2=== S | 20 | G=== 4 | -2 | 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | || | || | | | || |
+-||-+----+----+----+-||-+-||-+----+----+-||-+
| || | | | | || | || | | | || |
| 5 | -4=== 3===-6 | 4 | -9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6 | 4 | -5=== 6===-4 |
| | | | | | || | || | | |
+----+----+----+----+----+-||-+-||-+----+----+
| | | | | | || | || | | |
| 2 | -1 | 4 | -3 | 6 | -7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
| 9 | -9=== 8===-7=== 2===-5=== 3===-4 | 9 |
| | || | | | | | | || | |
+----+-||-+----+----+----+----+----+-||-+----+
| | || | | | | | | || | |
| -5=== 3 | -1 | 6 | -5=== 5 | -2 | 6===-8 |
| || | | | | || | || | | | || |
+-||-+----+----+----+-||-+-||-+----+----+-||-+
| || | | | | || | || | | | || |
| 5 | -4=== 3===-6 | 4 | -9=== 1 | -4=== 7 |
| || | || | | || | || | | || | || | |
+-||-+-||-+----+-||-+-||-+----+-||-+-||-+----+
| || | || | | || | || | | || | || | |
| -9 | 1 | -1 | 4===-8 | 7 | -7 | 5 | -1 |
| || | || | | | | | || | || | |
+-||-+-||-+----+----+----+----+-||-+-||-+----+
| || | || | | | | | || | || | |
| 4===-7 | 2=== S | 20 | G=== 4 | -2=== 3 |
| | | || | | | | | | || |
+----+----+-||-+----+----+----+----+----+-||-+
| | | || | | | | | | || |
| -4 | 5===-5 | 7 | -9=== 6 | -3 | 6 | -5 |
| | || | | | || | || | | | || |
+----+-||-+----+----+-||-+-||-+----+----+-||-+
| | || | | | || | || | | | || |
| 8 | -6 | 3===-6=== 1 | -8 | 5 | -1 | 3 |
| | || | || | | | || | | | || |
+----+-||-+-||-+----+----+-||-+----+----+-||-+
| | || | || | | | || | | | || |
| -3 | 1===-8 | 9 | -6=== 4 | -5=== 6===-4 |
| | | | | || | | || | | |
+----+----+----+----+-||-+----+-||-+----+----+
| | | | | || | | || | | |
| 2 | -1 | 4 | -3 | 6===-7=== 2 | -2 | 4 |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
Raw
script.py
from graphillion import GraphSet
n = int(raw_input())
a = []
for i in range(n):
a.append(map(int, raw_input().split()))
vi = [[i*n+j for j in range(n)] for i in range(n)]
iv = []
sg = []
for i in range(n):
for j in range(n):
iv.append((i,j))
if a[i][j] == 0:
sg.append(vi[i][j])
edges = []
weights = {}
for i in range(n):
for j in range(n):
for di,dj in [(1,0),(0,1)]: # (-1,0),(0,-1)
ni, nj = i+di, j+dj
if 0 <= ni < n and 0 <= nj < n:
v, u = vi[i][j], vi[ni][nj]
edges.append((v,u))
weights[(v,u)] = (a[i][j]+a[ni][nj])/2.0
GraphSet.set_universe(edges)
paths = GraphSet.paths(*sg)
def get_path():
for path in paths.max_iter(weights):
return path
path = get_path()
lh = ('-'*4).join(['+']*(n+1))
lv = (' '*4).join(['|']*(n+1))
s = [lh]
for i in range(n):
s.append(lv)
t = '|'
for j in range(n):
if a[i][j] != 0:
t += ' %2d |' % a[i][j]
else:
t += ' %s |' % ('S' if vi[i][j] == sg[0] else 'G')
s.append(t)
s.append(lv)
s.append(lh)
for i in range(len(s)):
s[i] = list(s[i])
score = 0
for v,u in path:
i,j = iv[v]
ni,nj = iv[u]
score += a[i][j]+a[ni][nj]
if i == ni:
for sj in range(3):
s[i*4+2][j*5+4+sj] = '='
else:
for si in range(3):
for sj in range(2):
s[i*4+3+si][j*5+2+sj] = '|'
print score/2
for t in s:
print ''.join(t)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment