「第4回 オフラインリアルタイムどう書く」参考問題: へなちょこ解答（Java）
鍋谷さんが第4回の参考問題を出してくださったので、解きました。
今回は、「フカシギの通行止め」です！
難易度と分量はこれを目安にと言いたいところだけれども、たぶんこれは難しすぎる。
こんなに難しい問題は出しませんよ、という意味で参考に。
ちょｗｗ その参考の仕方自体難しいｗｗ たしかに、これまでで最も時間がかかってしまいました。
自分の解答
Javaで書きました。とても長いです。
import static org.junit.Assert.assertEquals; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import org.junit.Test; public class Fukashigi { protected final String nodeStr = "abcdefghijklmnopqrstuvwxy"; // 行き先リスト protected List<List<Integer>> destDic; // すべての道順 protected List<String> allRoute; // 探索中の道順を保持 protected String tmpString = ""; public Fukashigi() { destDic = new ArrayList<List<Integer>>(); initAllNode(); } protected void initAllNode() { for (int i = 0; i < 24; i++) { List<Integer> tmp = new ArrayList<>(); if ((5 < i && i < 9) || (10 < i && i < 14) || (15 < i && i < 19)) { tmp = createRoute4(i); } else if ((i == 9) || (i == 14) || (i == 19)) { tmp = createRoute3E(i); } else if (20 < i && i < 24) { tmp = createRoute3S(i); } else if (i == 2 || i == 3) { tmp = createRoute3N(i); } else if (i == 10 || i == 15) { tmp = createRoute3W(i); } else if (i == 0 || i == 1 || i == 5) { tmp = createRoute2TL(i); } else if (i == 4) { tmp = createRoute2TR(i); } else if (i == 20) { tmp = createRoute2BL(i); } destDic.add(tmp); } } protected List<Integer> createRoute4(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 5); result.add(i - 1); result.add(i + 1); result.add(i + 5); return result; } protected List<Integer> createRoute3N(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 1); result.add(i + 1); result.add(i + 5); return result; } protected List<Integer> createRoute3E(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 5); result.add(i - 1); result.add(i + 5); return result; } protected List<Integer> createRoute3S(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 5); result.add(i - 1); result.add(i + 1); return result; } protected List<Integer> createRoute3W(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 5); result.add(i + 1); result.add(i + 5); return result; } protected List<Integer> createRoute2TL(int i) { List<Integer> result = new ArrayList<>(); result.add(i + 1); result.add(i + 5); return result; } protected List<Integer> createRoute2TR(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 1); result.add(i + 5); return result; } protected List<Integer> createRoute2BL(int i) { List<Integer> result = new ArrayList<>(); result.add(i - 5); result.add(i + 1); return result; } protected int execute(String input) { allRoute = new ArrayList<>(); createAllRoute(); List<String> result = new ArrayList<>(); List<String> endList = new ArrayList<>(); if (input.equals("") == false) { String[] deadends = input.split(" "); if (deadends != null && 0 < deadends.length) { for (String end0 : deadends) { String end1 = String.valueOf(end0.charAt(1)) + String.valueOf(end0.charAt(0)); endList.add(end0); endList.add(end1); } } } Iterator<String> routeite = allRoute.iterator(); for (; routeite.hasNext();) { String oneRoute = routeite.next(); boolean flag = false; Iterator<String> endite = endList.iterator(); for (; endite.hasNext();) { if (oneRoute.contains(endite.next())) { flag = true; } } if (flag == false) { result.add(oneRoute); } } return result.size(); } protected void createAllRoute() { tmpString = "a"; int startNode = 0; route(startNode); } protected void route(int nodeIndex) { // nodeIndexの次のノードのリストを得る List<Integer> destList = destDic.get(nodeIndex); // 次のノードそれぞれに対して、 Iterator<Integer> iterator = destList.iterator(); for (; iterator.hasNext();) { Integer nextNode = iterator.next(); // 同じ頂点を二度通ってはいけない char destChar = nodeStr.charAt(nextNode); if (-1 != tmpString.indexOf(String.valueOf(destChar))) { if (iterator.hasNext()) { continue; } else { return; } } tmpString += destChar; // 今加えたノードが終点であれば、1つのルートの完成 if (destChar == 'y') { allRoute.add(tmpString); tmpString = tmpString.substring(0, tmpString.length() - 1); return; } else { // 続きを探索 route(nextNode); tmpString = tmpString.substring(0, tmpString.length() - 1); } } } @Test public void testExecute() throws Exception { Fukashigi fuga = new Fukashigi(); assertEquals(8512, fuga.execute("")); assertEquals(4256, fuga.execute("af")); assertEquals(4256, fuga.execute("xy")); assertEquals(184, fuga.execute("pq qr rs st di in ns sx")); assertEquals(92, fuga.execute("af pq qr rs st di in ns sx")); assertEquals(185, fuga.execute("bg ch di ij no st")); assertEquals(16, fuga.execute("bc af ch di no kp mr ns ot pu rs")); assertEquals(0, fuga.execute("ab af")); assertEquals(0, fuga.execute("ty xy")); assertEquals(11, fuga.execute("bg ch ej gh lm lq mr ot rs sx")); assertEquals(18, fuga.execute("ty ch hi mn kp mr rs sx")); assertEquals(32, fuga.execute("xy ch hi mn kp mr rs sx")); assertEquals(50, fuga.execute("ch hi mn kp mr rs sx")); assertEquals(621, fuga.execute("ab cd uv wx")); assertEquals(685, fuga.execute("gh mn st lq qr")); assertEquals(171, fuga.execute("fg gl lm mr rs")); } }
問題ページ（http://qiita.com/items/9c514267214d3917edf2）のコメント欄に、もっとスマートなJava解答がupされていますので、ぜひそちらをご覧ください。
考え方の覚書き
コンストラクタの後に小さいメソッドが沢山あるのは、各ノードが"次のノード"をどの方向に何個持てるかを場合分けしたためです。
図にするとこんな感じです。
左上をスタート地点（0）、右下をゴール地点（24）とします。ゴール以外の各ノードは、次のノードを、1つ右（＋1）、1つ左（−1）、1つ上（−5）、1つ下（＋5）のいずれか（複数の場合もある）に持ちます。
上の図では、一点工夫をしています。
スタート地点と隣接するノードは、「同じ頂点を2回通ってはいけない」ルールにしたがい、スタート地点に戻ることができません。そこで、スタートの右隣を（±1, ＋5でなく）＋1, ＋5とみなしました。同様に、スタートの下隣を（＋1, ±5でなく）＋1, ＋5とみなしました。
- 各ノードの次のノードを辞書に保持する
- 深さ優先の全探索で、すべての経路を取得する
- 通行止め箇所を含む経路を除外する
（2012/9/20 追記）図の青と白の凡例が逆だったので修正。また、スタートの両隣を（＋1, ＋5）にした理由を追記しました。ご指摘ありがとうございます＞鍋谷さん
余談
今回の問題は、こちらの問題に似ていますね。
- JOI 2006-2007 予選 問題６
鍋谷さんは、あの狂気の動画「フカシギの数え方（http://www.youtube.com/watch?v=Q4gTV4r0zRs）」から着想を得られたそうで。やっぱり、問題集を出されたら売れると思います :-D
ちなみに、επιστημηさんが、JOIのほうの問題を解かれています。
上の解答で、STLのnext_permutation関数を知りました。組み合わせを列挙してくれるんですね。ベンリだなぁ。
- （参考）全ての組み合わせを作る【C++】 http://www.programming-magic.com/20090123132035/
