2843: 逛庙会
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：21
解决：5
题目描述
题目背景
NemoArce：我跟你说，你来北京，你就不能那种大的庙会，那都是坑外地游客的。
laowang：。。。
NemoArce：你要去你就得去这种规模小的，地道。
laowang：哦哦哦哦哦哦哦哦哦哦哦
题目描述：
NemoArce于是带着laowang去逛庙会了
NemoArce的家所在的区可以视为$N\times N$的矩阵$G$，N表示NemoArce的家；T表示庙会地点；.表示道路；#表示障碍物，无法通过。NemoArce决定带laowang开车去庙会。NemoArce家的车油箱可以视为无限大，但是初始时只有$M$单位的油。两人可以开车从一个位置到达另一个位置，但代价是花费$1$单位时间和$1$单位油。幸运的是，在区中有一个加油站，用G表示，如果两人能开车到达加油站的话，就可以加任意多的油。现在两人想知道，能否开车到达庙会，如果能，最少需要花费多少单位时间
NemoArce：我跟你说，你来北京，你就不能那种大的庙会，那都是坑外地游客的。
laowang：。。。
NemoArce：你要去你就得去这种规模小的，地道。
laowang：哦哦哦哦哦哦哦哦哦哦哦
题目描述：
NemoArce于是带着laowang去逛庙会了
NemoArce的家所在的区可以视为$N\times N$的矩阵$G$，N表示NemoArce的家；T表示庙会地点；.表示道路；#表示障碍物，无法通过。NemoArce决定带laowang开车去庙会。NemoArce家的车油箱可以视为无限大，但是初始时只有$M$单位的油。两人可以开车从一个位置到达另一个位置，但代价是花费$1$单位时间和$1$单位油。幸运的是，在区中有一个加油站，用G表示，如果两人能开车到达加油站的话，就可以加任意多的油。现在两人想知道，能否开车到达庙会，如果能，最少需要花费多少单位时间
输入
第$1$行，输入$N,\;M$
接下来$N$行，每行$N$个字符，表示矩阵$G$
接下来$N$行，每行$N$个字符，表示矩阵$G$
输出
若无解，输出$-1$，否则输出需花费的最少时间
样例输入 复制
3 5
N.#
.#T
...样例输出 复制
5提示
输入样例$2$
4 6
N.#G
#..#
##..
T...
输出样例$2$
-1
样例解释
对于样例$1$，可以从N到达T，花费5单位油和5单位时间
对于样例$2$，无法从N到达T，因为需花费$7$单位油$
数据范围
对于$20\%$的数据，$N\le 5$；
对于$40\%$的数据，$N\le 20
另有$10\%$的数据，矩阵中不存在`#`；
另有$10\%$的数据，矩阵中不存在`G`；
对于$100\%$的数据，$3\le N\le 10^3,\;M\le 10^6$，矩阵中只存在最多$1$个`G`，存在且仅存在$1$个`N`和`T`。
后记
laowang：你确定这就是你说的。。。庙会？
NemoArce：我也不知道今年它不办了啊。。。
4 6
N.#G
#..#
##..
T...
输出样例$2$
-1
样例解释
对于样例$1$，可以从N到达T，花费5单位油和5单位时间
对于样例$2$，无法从N到达T，因为需花费$7$单位油$
数据范围
对于$20\%$的数据，$N\le 5$；
对于$40\%$的数据，$N\le 20
另有$10\%$的数据，矩阵中不存在`#`；
另有$10\%$的数据，矩阵中不存在`G`；
对于$100\%$的数据，$3\le N\le 10^3,\;M\le 10^6$，矩阵中只存在最多$1$个`G`，存在且仅存在$1$个`N`和`T`。
后记
laowang：你确定这就是你说的。。。庙会？
NemoArce：我也不知道今年它不办了啊。。。