4797: OI联盟[202401]T5 迷宫
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
Jerry鼠为了躲避Tom猫的追打，逃进了一个迷宫，并且在迷宫内找到了一个格子睡觉。Tom一整天没有见到Jerry觉得无聊，于是决定去迷宫找Jerry，这个迷宫与寻常的迷宫有一些不一样：
a、这是是一个n*n大小的迷宫，迷宫每个小格子可能是墙、陷阱、路
b、为了简化这个问题，我们用#表示墙；用.表示路；用数字1--9表示陷阱
c、前面是墙的话，无法进入，当然Tom也无法走出迷宫范围（可以理解为迷宫四周都是墙，无法通行）
d、每个陷阱都有一个数字ki，表示Tom进入这个陷阱后需要ki*1000秒才能爬出这个陷阱，只有Tom爬出这个陷阱，才能继续走向下一个格子（1<=ki<=9）
e、Tom只能朝相邻的前后左右四个格子走，从当前所在的格子走向下一个格子固定花费100秒
现在Tom所在的格子为T，Jerry所在格子为J，请你帮Tom计算一下，他找到Jerry最少要花多少秒，如果永远都找不到Jerry，请输出Not Found。
输入
第一行为一个正整数n（10<=n<=400），表示这是一个n*n的迷宫。接下来有n行，每一行n个字符，表示这个迷宫的布局。
输出
输出一行，如果Tom能找到Jerry，则输出一个整数表示Tom找到Jerry所花的最少时间；如果Tom找不到Jerry，则输出Not Found。
样例输入 复制
5
T1...
2##..
.#...
.#1.1
..1.J
样例输出 复制
1800