{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003e《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng\u0027en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.\u003c/p\u003e \n\u003cp\u003e《西游记》(又称《猴子》)是中国文学四大名著之一。 它是由吴承恩在明代撰写的。 在这部小说中,孙悟空孙悟空,猪猪八戒和沙五经护送唐僧到印度去,得到神圣的佛教文字。\u003c/ p\u003e\n \u003cp\u003eDuring the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.\u003c/p\u003e \n\u003cp\u003e在旅途中,唐僧经常被恶魔俘虏。 大多数恶魔都想吃唐僧以达到永生,但一些女恶魔只是想嫁给他,因为他很帅。 因此,与恶魔战斗和拯救唐僧是孙悟空要做的主要工作。\u003c/ p\u003e\n \u003cp\u003eOnce, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace, and he wanted to reach Tang Monk and rescue him.\u003c/p\u003e \n\u003cp\u003e一次,唐僧被恶魔白骨头俘获。 白骨头住在宫殿里,她在房间里给唐僧打了个袖扣。 孙悟空设法进入了宫殿,他想到达唐僧并营救他。\u003c/ p\u003e\n \u003cp\u003eThe palace can be described as a matrix of characters. Different characters stand for different rooms as below:\u003c/p\u003e \n\u003cp\u003e宫殿可以描述为字符矩阵。 不同的字符代表不同的房间,如下所示:\u003c/ p\u003e\n \u003cp\u003e\u0027S\u0027 : The original position of Sun Wukong\u003c/p\u003e \n \u003cp\u003e\u0027T\u0027 : The location of Tang Monk\u003c/p\u003e \n \u003cp\u003e\u0027.\u0027 : An empty room\u003c/p\u003e \n \u003cp\u003e\u0027#\u0027 : A deadly gas room.\u003c/p\u003e \n \u003cp\u003e\u0027B\u0027 : A room with unlimited number of oxygen bottles. Every time Sun Wukong entered a \u0027B\u0027 room from other rooms, he would get an oxygen bottle. But staying there would not get Sun Wukong more oxygen bottles. Sun Wukong could carry at most 5 oxygen bottles at the same time.\u003c/p\u003e \n\u003cp\u003e\u0027B\u0027:一个房间的氧气瓶数量不限。 孙悟空每次从其他房间进入“ B”房间时,都会得到一个氧气瓶。 但是呆在那里不会给孙悟空更多的氧气瓶。 孙悟空最多可以同时携带5个氧气瓶。\u003c/ p\u003e\n \u003cp\u003e\u0027P\u0027 : A room with unlimited number of speed-up pills. Every time Sun Wukong entered a \u0027P\u0027 room from other rooms, he would get a speed-up pill. But staying there would not get Sun Wukong more speed-up pills. Sun Wukong could bring unlimited number of speed-up pills with him.\u003c/p\u003e \n\u003cp\u003e\u0027P\u0027:一个房间,里面有无限数量的加速药。 孙悟空每次从其他房间进入“ P”房间时,都会得到加速药丸。 但是,呆在那里不会给孙悟空更多的提速药。 孙悟空可以随身携带无限数量的加速药。\u003c/ p\u003e\n \u003cp\u003eSun Wukong could move in the palace. For each move, Sun Wukong might go to the adjacent rooms in 4 directions(north, west,south and east). But Sun Wukong couldn\u0027t get into a \u0027#\u0027 room(deadly gas room) without an oxygen bottle. Entering a \u0027#\u0027 room each time would cost Sun Wukong one oxygen bottle.\u003c/p\u003e \n\u003cp\u003e孙悟空可以进宫。 对于每一个举动,孙悟空可能会沿着四个方向(北,西,南和东)前往相邻的房间。 但是孙悟空没有氧气瓶就无法进入“#”室(致命的气体室)。 每次进入“#”房间将花费孙悟空一个氧气瓶。\u003c/ p\u003e\n \u003cp\u003eEach move took Sun Wukong one minute. But if Sun Wukong ate a speed-up pill, he could make next move without spending any time. In other words, each speed-up pill could save Sun Wukong one minute. And if Sun Wukong went into a \u0027#\u0027 room, he had to stay there for one extra minute to recover his health.\u003c/p\u003e \n\u003cp\u003e每一步都花了孙悟空一分钟。 但是,如果孙悟空吃了加速药丸,他就可以不花任何时间采取下一步行动。 换句话说,每颗提速药丸可以为孙悟空节省一分钟。 如果孙悟空进入“#”房间,他必须再呆一分钟才能恢复健康。\u003c/ p\u003e\n \u003cp\u003eSince Sun Wukong was an impatient monkey, he wanted to save Tang Monk as soon as possible. Please figure out the minimum time Sun Wukong needed to reach Tang Monk.\u003c/p\u003e \n\u003cp\u003e由于孙悟空是个不耐烦的猴子,他想尽快拯救唐僧。 请计算出孙悟空到达唐僧所需的最短时间。\u003c/ p\u003e\n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThere are no more than 25 test cases.\u003c/p\u003e \n \u003cp\u003eFor each case, the first line includes two integers N and M(0 \u0026lt; N,M ≤ 100), meaning that the palace is a N × M matrix. \u003c/p\u003e \n \u003cp\u003eThen the N×M matrix follows.\u003c/p\u003e \n \u003cp\u003eThe input ends with N \u003d 0 and M \u003d 0.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case, print the minimum time (in minute) Sun Wukong needed to save Tang Monk. If it\u0027s impossible for Sun Wukong to complete the mission, print -1\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e2 2\nS#\n#T\n2 5\nSB###\n##P#T\n4 7\nSP.....\nP#.....\n......#\nB...##T\n0 0\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e-1\n8\n11\u003c/pre\u003e \n "}}]}