CodeIQ過去問集36：まっすぐ行こう

本稿はCodeIQで2016年7月12日～2018年4月25日に出題された 【実力判定：Sランク】まっすぐ行こう という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

まっすぐ行こう

【問題】

M×Nのマス目を左上から右下に向かって移動します。移動方向は上下左右のみです。 ただし、マス目上には通れない箇所がいくつかあります。同じ点を2回以上通過しても構いません。

上図の黄色い部分をスタート、青い部分をゴールとし、黒い部分は通れないものとします。 このとき、スタートからゴールまでの経路はいくつか考えられますが、できるだけ方向転換の回数が少ない経路を見つけてください。

左図の経路では方向転換（★印の部分が）2か所ですが、右図では方向転換が1か所だけですので、このケースでは1回の方向転換でゴールまで到達できることになります。

【入力】

標準入力から、1行目に半角スペースで区切られた2つの整数値M, N（1≦M, N≦64）が与えられます。 2行目から（M+1)行目までは長さNの文字列です。文字列は、' .'と'#'で構成されています。 '.'は移動できる部分、'#'は移動できない部分を表します。 2行目の1文字目と、（M+1）行目のN文字目、つまりスタート地点とゴール地点に相当する点は必ず'.'になっています。 また、スタートからゴールに到達する経路が必ず存在するものとします。

【出力】

マス目の左上から右下まで移動する経路の中で、方向転換する回数の最小値を、標準出力に出力してください。

【入出力サンプル】

Input

2 3
..#
...

Output

1

【解答方法】

[massugu.zip]をダウンロードし、展開してください。中には以下のフォルダが含まれています。

• input: テストデータです
• output: 解答データです

テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。

（解説は後日）