Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

You have a square maze of size N x N. You begin from a source cell and start your journey in hope of reaching the target cell in minimum number of moves. You can move to new cell if it shares an edge with the current cell you are standing on. The minimum moves required aren’t always the Manhattan distance as there are few obstacles placed on certain places of the maze. You have to avoid those obstacles in your path. In addition to the obstacles, there are more impediments in the form of guards. The guards, however, aren’t that clever and they are also short-sighted. Initially every guard monotonously walks to the right. If it encounters an obstacle or reaches the end of the maze (last column) it turns left and starts walking. It walks left until it reaches an obstacle or the end (first column) when it changes direction to the right and starts walking. Every guard moves 1 cell per unit time. Your speed is also 1 cell per unit time. In every unit time, you can either make a move or stay in the same position. Staying in the same position also counts as a move.

You are caught by a guard if both of you land on the same cell at the same time or if you bump into each other during a move. In the latter case, you are caught in between the cells.

Every cell of the maze will be represented by one of the following:

S – Starting Cell.

T – Target Cell.

# - An Obstacle

X – A Guard

. – An Empty Cell

There will be at most 3 guards in a maze and all of them will be situated in different rows.

An example of the movement of a guard for first 6 seconds of its locomotion:

......     ......     ......     ......     ......     ......    ......
......     ......     ......     ......     ......     ......    ......
.#.X..     .#..X.     .#...X     .#..X.     .#.X..     .#X...    .#.X..
......     ......     ......     ......     ......     ......    ......
  0          1          2          3         4          5          6     

Input

The input file starts with an integer T(T<50) that indicates the number of test cases. Each case starts with a positive integer N(N<10). The next N lines contain N characters each that fill up the maze. There will be exactly one S character and one T character. There will be no more than 3 X characters in the maze.

Output

For each input, output the case number followed by the minimum number of moves required. If it is impossible to reach the target, output -1 instead.

ProblemSetter: Sohel Hafiz
Special Thanks: Vinay Singh

題目描述：

首先給一張地圖，求 S 到 T 的最短路徑，中間會有水平移動的障礙物 'X'。
每一行最多只會有一個 'X'，也就是說同一行只會有一個 'X' 才不會 'X' 之間相撞。
整張地圖最多有 3 個 'X'。

所有 'X' 一開始皆往右邊行進，每隔一秒會持續動作，中間過程為彈性碰撞。

從 S 到 T 的過程中，可以選擇上下左右或者是不動，但不能接觸到障礙物，也不能與障礙物進行穿越。

題目解法：