{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n Tower Defence is a popular classic game. During the game, there will appear some monsters at the entry and each will find a shortest path to the exit. Your task is puting some warriors on the map to kill the monsters before they reach exit.\u003cbr\u003e\n \u003ccenter\u003e\n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/10cd1080be5290ab97f0b3743a32b514?v\u003d1679361242\"\u003e\n \u003c/center\u003e\u003cbr\u003e\n You could put warrior(infinite) on the map to change the pathes of monsters. Of course, the longer the path is, the more advantageous to you. \u003cbr\u003e\n Now, giving you the information of the map, how do you put the warriors to make the monsters move on the longest path?\u003cbr\u003e\n The meaning of each character in the map:\u003cbr\u003e\n \u0027S\u0027 represents the entry of the map, one and only one;\u003cbr\u003e\n \u0027T\u0027 represents the exit of the map, one and only one;\u003cbr\u003e\n \u0027.\u0027 represents the grid that monster could move on;\u003cbr\u003e\n \u0027B\u0027 represents the barrier that monster couldn\u0027t move on;\u003cbr\u003e\n \u0027W\u0027 represents the warrior that you put.(could only put on \u0027.\u0027)\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line is a number T(1\u0026lt;\u003dT\u0026lt;\u003d30), represents the number of case. The next T blocks follow each indicates a case.\u003cbr\u003e\nThe first line of each case contains two integers N, M (3\u0026lt;\u003dN\u0026lt;\u003d20 , 3\u0026lt;\u003dM\u0026lt;\u003d9)\u003cbr\u003e\nThen N lines follow, each line contains M chars represent the map, include \u0027S\u0027,\u0027T\u0027,\u0027.\u0027,\u0027B\u0027.\u003cbr\u003e\nI promise there must be at least one way from entry to exit."}},{"title":"Output","value":{"format":"HTML","content":"For each case, first line output the number of case with the longest distance from S to T.(as shown in the sample output)\u003cbr\u003e\nThen output any one of these ways, using the same format for the map as in the input. Output a blank line after each case.(Special judge.If you not output a blank line after each case, you will get Wrong Answer)"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e4\r\n3 3\r\nS..\r\n...\r\n..T\r\n\r\n5 5\r\nS....\r\n.B.B.\r\n.....\r\n.B.B.\r\n....T\r\n\r\n5 5\r\nS...T\r\n..B..\r\n..B..\r\n..B..\r\n.....\r\n\r\n5 5\r\nS...T\r\n..B..\r\n..B..\r\n..B..\r\n..B..\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003eCase 1: 5\r\nS..\r\n...\r\n..T\r\n\r\nCase 2: 17\r\nS....\r\nWBWB.\r\n.....\r\n.BWBW\r\n....T\r\n\r\nCase 3: 17\r\nS.W.T\r\nW.B.W\r\n..B..\r\n.WBW.\r\n.....\r\n\r\nCase 4: 5\r\nS...T\r\n..B..\r\n..B..\r\n..B..\r\n..B..\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}