import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random, core.bitop; import std.string, std.regex, std.conv, std.stdio, std.typecons; struct point { int x, y; point opBinary(string op)(point rhs) { static if (op == "+") return point(x + rhs.x, y + rhs.y); else static if (op == "-") return point(x - rhs.x, y - rhs.y); } } const auto sibPoints = [point(-1, 0), point(0, -1), point(1, 0), point(0, 1)]; alias Tuple!(point, "curr", point, "prev", size_t, "len") qItem; void main() { auto rd = readln.split.map!(to!size_t); auto w = rd[0], h = rd[1]; auto mij = iota(h).map!(_ => readln.split.map!(to!int).array).array; bool valid(point p) { return p.x >= 0 && p.x < w && p.y >= 0 && p.y < h; } bool isKadomatsu(point p1, point p2, point p3) { auto m1 = mij[p1.y][p1.x], m2 = mij[p2.y][p2.x], m3 = mij[p3.y][p3.x]; return m1 != m2 && m2 != m3 && (m1 > m2 && m3 > m2 || m1 < m2 && m3 < m2); } int calc() { auto visited = new bool[][](h, w); auto queue = new DList!qItem(qItem(point(0, 1), point(0, 0), 1), qItem(point(1, 0), point(0, 0), 1)); auto goal = point(w.to!int - 1, h.to!int - 1); visited[0][0] = true; visited[1][0] = true; visited[0][1] = true; while (!queue.empty) { auto qi = queue.front; queue.removeFront; foreach (sib; sibPoints) { auto np = qi.curr + sib; if (!valid(np) || visited[np.y][np.x] || !isKadomatsu(np, qi.curr, qi.prev)) continue; if (np == goal) return qi.len.to!int + 1; queue.insertBack(qItem(np, qi.curr, qi.len + 1)); } } return -1; } writeln(calc); }