range = xrange input = raw_input def solve(): W, H, hsWH, hsHW = read_data() Es = build_edges(W, H, hsWH, hsHW) return wfs(Es, W, H) def read_data(): W, H, N = map(int, input().split()) hsWH = [[0] * H for w in range(W)] # vertical lines hsHW = [[0] * W for h in range(H)] # horizontal lines for n in range(N): process_move(hsWH, hsHW, W, H) return W, H, hsWH, hsHW def process_move(hsWH, hsHW, W, H): Mnotused = input() Bs = list(map(int, input().split())) h0, w0 = divmod(Bs[0], W) for b in Bs: h1, w1 = divmod(b, W) if h0 == h1: # horizontal move if w0 > w1: hsHW[h0][w1] += 1 hsHW[h0][w0] -= 1 else: hsHW[h0][w0] += 1 hsHW[h0][w1] -= 1 w0 = w1 else: # vertical move if h0 > h1: hsWH[w0][h1] += 1 hsWH[w0][h0] -= 1 else: hsWH[w0][h0] += 1 hsWH[w0][h1] -= 1 h0 = h1 def build_edges(W, H, hsWH, hsHW): Es = [[0, 0, 0, 0] for idx in range(H * W)] process_vertical_move(W, H, hsWH, Es) process_horizontal_move(W, H, hsHW, Es) return Es def process_vertical_move(W, H, hsWH, Es): for w, hsw in enumerate(hsWH): cum = 0 idx = w for val in hsw: cum += val if cum: Es[idx][3] = 1 Es[idx + W][2] = 1 idx += W def process_horizontal_move(W, H, hsHW, Es): for h, hsh in enumerate(hsHW): cum = 0 idx = h * W for val in hsh: cum += val if cum: Es[idx][1] = 1 Es[idx + 1][0] = 1 idx += 1 def wfs(Es, W, H): '''Es[idx][d]: セルidx番のd方向の辺の有無。(d=0,1,2,3=左、右、下、上=-1,1,-W,W) idx=0 から、idx=H*W-1 までの最短距離を幅優先探索で求める。 ''' start = 0 goal = H * W - 1 unvisited = [True] * (H * W) frontiers = [start] cost = 0 while frontiers: cost += 1 new_frontiers = [] for f in frontiers: if f == goal: return cost - 1 Esf = Es[f] if Esf[0] and unvisited[f - 1]: unvisited[f - 1] = False new_frontiers.append(f - 1) if Esf[1] and unvisited[f + 1]: unvisited[f + 1] = False new_frontiers.append(f + 1) if Esf[2] and unvisited[f - W]: unvisited[f - W] = False new_frontiers.append(f - W) if Esf[3] and unvisited[f + W]: unvisited[f + W] = False new_frontiers.append(f + W) frontiers = new_frontiers return -1 ans = solve() if ans == -1: print("Odekakedekinai..") else: print(ans)