ガジェット通信

見たことのないものを見に行こう

第90回「今週のアルゴリズム:突進するイノシシ」正解者発表

DATE:
  • ガジェット通信を≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第90回は「今週のアルゴリズム:突進するイノシシ」の問題です。

問題文「第90回 突進するイノシシ」

「猪突猛進」という言葉があるように、イノシシはまっすぐに突き進むことで有名です。
図のようなマス目があったとします。
イノシシは進む方向を決めると、その方向に向かって壁や障害物に当たるまで突き進みます。

壁や障害物に到達すると、左右どちらかに向きを変えて、突き進むことを繰り返します。
このことを繰り返しながら、最短距離で餌にたどり着くまでの経路を考えます。
このとき、壁や障害物に当たった回数を数えます。

周囲を壁に囲まれた中で、次の図のようにイノシシと餌が位置しているとき、
右の図のように移動すると最短距離で餌にありつけます。
この場合は3回になります。

標準入力から障害物の位置が与えられたとき、
イノシシと餌を障害物以外の位置に適当に配置し、餌にたどり着くまでの経路を考えます。
(イノシシが餌に到達できない場合は、壁や障害物に当たる回数は0回とします。)
壁や障害物に当たる回数が最大になるような配置を考え、その回数を答えてください。

上記の図の場合、標準入力から以下のように与えられます。
一行目にはマスのサイズ n が与えられ、n × n のマス目について、
二行目以降に、障害物の位置が「X」、障害物がない位置が「O」で与えられます。

【入出力サンプル】
標準入力
5
OOXOO
XOOOO
OOOOO
OOOOO
XOXXO

標準出力
6

今回の場合、以下のように猪と餌を配置したときが壁や障害物に当たる回数が最大になり、
その回数は6回ですので、標準出力に「6」を出力します。
なお、入力される大きさ n は最大で7とします。

正解者

おめでとうございます!正解者のみなさんです。(新着順)

Azicore様 

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。