1696: 马腿上的最短路
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：6
Solved：4
Description
在一个 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。
Input
输入包含多组数据，以 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
Output
对于每组数据，输出所求的最少步数。若不能到达（包含起点或终点被占用的情况），则输出 No solution!。
Sample Input Copy
4 4 0 0 3 2
0010
0000
0000
0001
4 4 0 0 3 2
0010
0000
0100
0001
Sample Output Copy
3
No solution!