两名宇航员在探索一个未知行星,行星上有一些障碍物,这些障碍物用数字1表示,没有障碍物用数字0表示。行星被表示成一个N*M的矩阵。探索过程中两名宇航员走散了。已知A宇航员的位置(x1,y1)和B宇航员的位置(x2,y2),请你帮助A宇航员找到一条最短路径到达B宇航员的位置,并输出最短路径的长度(不包括起点)。
注意:
1.x1、x2表示矩阵的行号,y1、y2表示矩阵的列号;
2.左上角的位置为(0,0);
3.A、B宇航员的位置只能在数字0上;
4.有障碍物的位置不能通过。
例如:当 N=4,M=5,x1=1,y1=0,x2=3,y2=3,A宇航员的位置(1,0),B宇航员的位置(3,3),矩阵表示如下:
其中,从A到B的最短路线用箭头表示,最短路线长度为7。
【输入描述】第一行输入两个正整数N,M,正整数之间以空格隔开
接下来的N行,每行输入M个数,数字1表示障碍物,数字0表示没有障碍物,数字之间以空格隔开,第N+2行输入四个整数,分别表示x1,y1,x2,y2,整数之间以空格隔开
【输出描述】输出一个数,表示A宇航员到达B宇航员位置的最短路径的长度(不包括起点)
【样例输入】
4 5
0 0 0 0 0
0 1 0 1 0
0 1 0 0 0
0 0 1 0 0
1 0 3 3
【样例输出】
7