{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e「西遊記」(または「孫悟空」)は、中国文学の四大古典小説の1つです。明代の吳承恩によって書かれました。この小説では、孫悟空(猿の王)、豬八戒、沙悟浄が唐僧をインドに護衛して聖なる仏教の経典を取りに行くというストーリーが描かれています。\u003c/p\u003e \n \u003cp\u003e旅の途中で、唐僧はよく悪魔に捕まりました。ほとんどの悪魔は不老不死になるために唐僧を食べたがりましたが、美しい女性の悪魔たちは彼を結婚したがっていました。なぜなら彼はイケメンだったからです。そのため、悪魔と戦い、唐僧を助けることが孫悟空の主な仕事でした。\u003c/p\u003e \n \u003cp\u003eある時、唐僧は骨精の悪魔に捕まりました。骨精は宮殿に住んでおり、彼女は唐僧を部屋に閉じ込めました。孫悟空は宮殿に入ることに成功し、唐僧を助け出そうとしました。\u003c/p\u003e \n \u003cp\u003e宮殿は文字の行列に例えられます。異なる文字が異なる部屋を表します:\u003c/p\u003e \n \u003cp\u003e\u0027S\u0027:孫悟空の元の位置\u003c/p\u003e \n \u003cp\u003e\u0027T\u0027:唐僧の位置\u003c/p\u003e \n \u003cp\u003e\u0027.\u0027:空の部屋\u003c/p\u003e \n \u003cp\u003e\u0027#\u0027:有毒ガスのある部屋\u003c/p\u003e \n \u003cp\u003e\u0027B\u0027:無制限の酸素ボトルがある部屋。孫悟空が他の部屋から\u0027B\u0027部屋に入るたびに、酸素ボトルを1つ手に入れることができます。しかし、そこに滞在しても、孫悟空には酸素ボトルが増えません。孫悟空は同時に最大5つの酸素ボトルを持つことができます。\u003c/p\u003e \n \u003cp\u003e\u0027P\u0027:無制限のスピードアップの薬がある部屋。孫悟空が他の部屋から\u0027P\u0027部屋に入るたびに、スピードアップの薬を1つ手に入れることができます。しかし、そこに滞在しても、孫悟空にはスピードアップの薬が増えません。孫悟空は無制限のスピードアップの薬を持つことができます。\u003c/p\u003e \n \u003cp\u003e孫悟空は宮殿内を動くことができます。各移動では、孫悟空は4方向(北、西、南、東)の隣接する部屋に移動することができます。しかし、孫悟空は酸素ボトルなしで\u0027#\u0027部屋(有毒ガスのある部屋)に入ることはできません。\u0027#\u0027部屋に入るたびに、孫悟空に1つの酸素ボトルが必要です。\u003c/p\u003e \n \u003cp\u003e各移動には1分かかります。しかし、孫悟空がスピードアップの薬を飲むと、次の移動を時間をかけずに行うことができます。つまり、それぞれのスピードアップの薬は1分を節約することができます。そして、孫悟空が\u0027#\u0027部屋に入ると、健康を回復するために1分間そこに滞在しなければなりません。\u003c/p\u003e \n \u003cp\u003e孫悟空は我慢ができない猿であるため、できるだけ早く唐僧を助けたかったのです。孫悟空が唐僧に到達するために必要な最小時間を求めてください。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eテストケースは25個を超えません。\u003c/p\u003e \n \u003cp\u003e各ケースについて、最初の行には2つの整数NとM(0<N、M≤100)が含まれており、これは宮殿がN×Mの行列であることを意味します。\u003c/p\u003e \n \u003cp\u003eその後にN×M行列が続きます。\u003c/p\u003e \n \u003cp\u003e入力はN \u003d 0 および M \u003d 0 のときに終了します。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e各テストケースについて、孫悟空が唐僧を救うために必要な最小時間(分単位)を出力してください。孫悟空が任務を達成することができない場合は、-1を出力してください。\u003c/p\u003e \n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\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"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e-1\r\n8\r\n11\u003c/pre\u003e"}}]}