import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class Main{ private int w; private int h; /* 4bitを上下左右へ移動可能かどうかのフラグとして扱う。 */ private boolean[][] blocks; private static final String ODEKAKEDEKINAI = "Odekakedekinai.."; public Main(int w, int h, int[][] b) { this.w = w; this.h = h; blocks = new boolean[w * h][5]; for (int i = 0; i < b.length; i++) { for (int j = 0; j < b[i].length - 1; j++) { footprint(b[i][j], b[i][j + 1]); } } } private void execute() { /* block[0]を起点として、移動開始 */ Set next = new HashSet(); next.add(0); int stepCount = 0; while (true) { next = step(next); stepCount++; if (next.isEmpty()) { System.out.println(ODEKAKEDEKINAI); break; } if (next.contains(w * h - 1)) { System.out.println(stepCount); break; } } } /** * StepCount歩数目にはじめて踏破するblcoksのNumberを記録して返す * * @param stepCount */ private Set step(Set beforeBlocks) { Set nextBlocks = new HashSet(); for (int number : beforeBlocks) { /* 現在numberに踏破済みのフラグ(blocks[number][4]=true)を立てる */ blocks[number][4] = true; /* 上移動チェック */ if (blocks[number][0] && !blocks[number + w][4]) { nextBlocks.add(number + w); } /* 下移動チェック */ if (blocks[number][1] && !blocks[number - w][4]) { nextBlocks.add(number - w); } /* 左移動チェック */ if (blocks[number][2] && !blocks[number - 1][4]) { nextBlocks.add(number - 1); } /* 右移動チェック */ if (blocks[number][3] && !blocks[number + 1][4]) { nextBlocks.add(number + 1); } } return nextBlocks; } private void footprint(int b1, int b2) { int min = Math.min(b1, b2); int max = Math.max(b1, b2); if (min / w == max / w) { /* 横の移動 = minとmaxをwで割ったときの値が等しい */ for (int i = min; i < max; i++) { /* 左側(数が小さいほうのblock)から右へと移動できるので、blocks[i][3]をtrue */ blocks[i][3] = true; /* 右側(数が大きいほうのblock)から左へと移動できるので、blocks[i+1][2]をtrue */ blocks[i + 1][2] = true; } } else { /* 縦の移動 */ for (int i = min; i < max; i += w) { /* 下側(数が小さいほうのblock)から上へと移動できるので、blocks[i][0]をtrue */ blocks[i][0] = true; /* 上側(数が大きいほうのblock)から下へと移動できるので、blocks[i+w][1]をtrue */ blocks[i + w][1] = true; } } } public static void main(String[] args) { Scanner cin = new Scanner(System.in); List lines = new ArrayList(); while (cin.hasNext()) { lines.add(cin.nextLine()); } cin.close(); String[] blockStr = lines.get(0).split(" "); int w = Integer.parseInt(blockStr[0]); int h = Integer.parseInt(blockStr[1]); int[][] blockInfo = new int[Integer.parseInt(blockStr[2])][]; for (int i = 0; i < blockInfo.length; i++) { int stepCount = Integer.parseInt(lines.get(2 * i + 2)); blockInfo[i] = new int[stepCount + 1]; String[] blockInfoStr = lines.get(2 * i + 3).split(" "); for (int j = 0; j < blockInfo[i].length; j++) { blockInfo[i][j] = Integer.parseInt(blockInfoStr[j]); } } Main snow = new Main(w, h, blockInfo); snow.execute(); } }