shortest-path's Introduction

shortest-path

人材獲得作戦・４　試験問題ほかをTypeScriptで解く。

問題

縦Nマス*横Mマスの、壁とスペースから成る迷路が与えられる。迷路の中にはスタートマスとゴールマスが一つずつある。スタートマスからゴールマスに至る最短経路を求める。

より正確な条件としては

壁は*、移動可能なマスは (半角スペース)で表す。
スタートマスはS、ゴールマスはGで表す。
入出力はテキストデータを用いる。
一度に動けるのは上下左右のみ。
最短経路が複数ある場合、そのうち一つだけを出力すれば良い。

を採用する。

例

以下のような入力が与えられた場合、次のようなテキストデータを出力をする。

（入力データ）
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

（出力データ）
**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$* $$* $$$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

Recommend Projects