module main; // https://kmjp.hatenablog.jp/entry/2015/07/14/0930 より // 2次元グリッド、幅優先探索 import std; // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } alias P = Tuple!(int, "y", int, "x"); auto dir = [P(-1, 0), P(0, 1), P(1, 0), P(0, -1)]; int N, V, sx, sy, gx, gy; int[][] L; int[][][] HP; void main() { // 入力 readln.chomp.formattedRead("%d %d %d %d %d %d", N, V, sx, sy, gx, gy); sx--, sy--, gx--, gy--; auto L = new int[][](N); foreach (ref row; L) row = readln.split.to!(int[]); // 答えの計算と出力 HP = new int[][][](2, N, N); HP[0][sy][sx] = V; foreach (i; 0 .. 10_001) { int cur = i % 2, tar = cur ^ 1; fill(HP[tar], 0); foreach (y; 0 .. N) { foreach (x; 0 .. N) { if (HP[cur][y][x] <= 0) continue; foreach (d; dir) { int ty = y + d.y, tx = x + d.x; if (ty < 0 || ty >= N || tx < 0 || tx >= N) continue; if (HP[cur][y][x] > L[ty][tx]) HP[tar][ty][tx] = max(HP[tar][ty][tx], HP[cur][y][x] - L[ty][tx]); } } } if (HP[tar][gy][gx] > 0) { writeln(i + 1); return; } } writeln(-1); }