{"trustable":true,"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\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\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\u003eThe palace can be described as a matrix of characters. Different characters stand for different rooms as below:\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\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\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\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\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 "}},{"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\r\nS#\r\n#T\r\n2 5\r\nSB###\r\n##P#T\r\n4 7\r\nSP.....\r\nP#.....\r\n......#\r\nB...##T\r\n0 0\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e-1\r\n8\r\n11\u003c/pre\u003e \n "}}]}