1529 : 探亲

时间限制:1 Sec 内存限制:64 MiB 提交:131 正确:32

提交 状态 论坛

题目描述

kcxz在过年的时候需要到亲戚家探亲,他首先要到他姨爷家探亲,然后再从姨爷家到他的舅舅家。请你帮助kcxz算一算最短路程来让kcxz节约时间。kcxz所在的城市简单地看成是一个矩形,kcxz每次只能向上或向下或向左或向右行走一格,并且不能离开这个城市。

输入描述

第一行一个整数代表测试的组数。 对于每组数据,第一行两个整数,代表kcxz所在城市的行数和列数。之后行,每行有个字符,'.'表示这个位置可以走,'*'表示这个位置是障碍物不可以走。之后一行6个整数,分别表示kcxz家、kcxz的姨爷家、kcxz的舅舅家的坐标。代表行,代表列。这三个坐标不会相同,并且没有障碍物。()

输出描述

输出行,每行一个数来代表kcxz走的最少步数。如果不能到达姨爷家或者不能到达舅舅家,则输出"-1"(不带引号)。

样例输入

1
3 4
....
.***
...*
1 4 1 2 3 1

样例输出

5

来源

蓝桥杯2021预选