1796: 马腿上的最短路
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
在一个 n*m 的棋盘上有一些点已被己方棋子占用。有一只马要从点 S(x_s, y_s) 走到点 T(x_t, y_t) ，现求一个步数最少的方案。马的每一步是这样走的：先从起点 A 向上下左右任意方向走 1 格经过点 B，再顺时针或逆时针旋转 π/4 后走 sqrt(2) 格到达点C。但这是中国象棋里的马而不是国际象棋里的 knight，即如果经过的点 B 被占用，则会发生“蹩（bié）马腿”不能这样走。只有当B 与 C 都未被占用时马才能从 A 跳到 C。
输入
输入包含多组数据，以 EOF 结束。
每组数据第一行包含六个整数m，n，x_s，y_s，x_t，y_t。接下来 n 行给出一个 n*m 的〇一矩阵，其中 1 表示已经被占用的格子。
0 < m, n <= 100
0 <= x_s, x_t < n
0 <= y_s, y_t < m
输出
对于每组数据，输出所求的最少步数。若不能到达（包含起点或终点被占用的情况），则输出 No solution!。
样例输入 复制
4 4 0 0 3 2
0010
0000
0000
0001
4 4 0 0 3 2
0010
0000
0100
0001
样例输出 复制
3
No solution!