おじい研究所

主にプログラミングの話題です

CodeIQ過去問集40:欲張り団子

本稿はCodeIQで出題予定だったものの事情があって出題できなかった 【実力判定:Sランク】欲張り団子 という問題です。 Sランクとありますがだいぶヌルいです。

欲張り団子

【問題】

正方形のマス目があります。
マス目のいくつかには団子があります。
この団子に、タテ・ヨコ・ナナメ(水平方向から±45度)の方向から串を刺して団子を取ります。
このとき、できるだけ少ない本数の串ですべての団子を取る方法を考え、串の本数の最小値を答えてください。

f:id:Ozy:20180502203807p:plain

たとえばこのような配置の場合、次のように2本の串ですべての団子を取ることができます。

f:id:Ozy:20180502203818p:plain

【入力】

標準入力から、次の値が与えらえます。
1行目には、正方形の一辺のサイズN(8以下の正の整数)、
2行目以降のN行分は長さNの文字列で、団子がある場所を示す「o」、団子がない場所を示す「x」のいずれかになっています。

【出力】

すべての団子を取るのに必要な串の本数の最小値(値のみ)を出力してください。

【入出力サンプル】

Input

3
ooo
xox
oxx

Output

2

【解答方法】

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

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

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

[【解答例】]


こっちは古い版