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

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

欲張り団子

【問題】

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

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

【入力】

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

【出力】

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

【入出力サンプル】

Input

3
ooo
xox
oxx

Output

2

【解答方法】

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

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

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

[【解答例】]