Description

这有一个迷宫，有0~8行和0~8列： 1,1,1,1,1,1,1,1,1 1,0,0,1,0,0,1,0,1 1,0,0,1,1,0,0,0,1 1,0,1,0,1,1,0,1,1 1,0,0,0,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,0,0,0,1 1,1,1,1,1,1,1,1,1 0表示道路，1表示墙。 现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？ 注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从( 3 , 1 )到（ 4 , 1 )

Input Format

第一行输入一个整数n（0 < n <= 100），表示有n组测试数据; 随后n行,每行有四个整数a,b,c,d（0 <= a,b,c,d <= 8）分别表示起点的行、列，终点的行、列。

Output Format

输出最少走几步。

2
3 1 5 7
3 1 6 7​

12
11​

Source

搜索