体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

『【誕生日問題10月】金山をたくさんプレゼント』 解答と解説

【誕生日問題10月】金山をたくさんプレゼント

本問題は、10月誕生日の人へ向けた、コーディング問題でした。

それでは以下、問題とその解答、解説を見ていきましょう。

問題

あなたは誕生日プレゼントとして、土地をもらえることになりました。

もらえる土地は、5×5マスの正方形の土地です。

世界は10×10のマスでできており、いくつかのマスには金山があります。金山の数が最大になる5×5マスは、1つしかありません。

最も多くの金山をゲットできるように、もらえる土地を探索するプログラムを書いて下さい。

以下、入力の例です。左上を {“x”:0,”y”:0} として、右下を {“x”:9,”y”:9} とします。「x」はx座標、「y」はy座標です。通常の土地は「w」の文字、金山のある土地は「G」の文字です。

これらは標準入力から、改行で区切られた文字として渡されます。

wwGwwwwwGG
Gwwwwwwwww
wwwwwwwwww
Gwwwwwwwww
wwwwGwwGww
wGwwwwwwww
wwwGGwwwww
wwwwwwGwww
wwwwGGwwww
GwwwGGwGwG

以下、出力の例です。最も多くの金山が得られる土地の左上の座標を、「{“x”:3,”y”:5,”g”:8}」のように答えます。「x」はx座標、「y」はy座標、「g」は5×5マスの土地に含まれる金山の数です。

答えは、以下のように標準出力に出力してください。

{“x”:3,”y”:5,”g”:8}

上記の答えを図解すると、下のような土地になります。

wwG wwwww GG
Gww wwwww ww
www wwwww ww
Gww wwwww ww
www wGwwG ww
+—–+
wGw|wwwww|ww
www|GGwww|ww
www|wwwGw|ww
www|wGGww|ww
Gww|wGGwG|wG
+—–+

入力と出力

入力1と出力1

// 入力1
wwGwwwwwGG
Gwwwwwwwww
wwwwwwwwww
Gwwwwwwwww
wwwwGwwGww
wGwwwwwwww
wwwGGwwwww
wwwwwwGwww
wwwwGGwwww
GwwwGGwGwG

// 出力1
{“x”:3,”y”:5,”g”:8}

// 図1
wwG wwwww GG
Gww wwwww ww
www wwwww ww
Gww wwwww ww
www wGwwG ww
+—–+
wGw|wwwww|ww
www|GGwww|ww
www|wwwGw|ww
www|wGGww|ww
Gww|wGGwG|wG
+—–+

入力2と出力2

// 入力2
wwwwwwwGww
wwGGwwwGww
wwwwGwwwww
wGwwwwwwww
wwwwwGGwGG
wwwwwwGwww
wwwwGGwGww
wwwwwGwGGw
wwGGwwGwGG
wwGwGwwGwG

// 出力2
{“x”:5,”y”:4,”g”:13}

// 図2
wwwww wwGww
wwGGw wwGww
wwwwG wwwww
wGwww wwwww
+—–+
wwwww|GGwGG|
wwwww|wGwww|
wwwwG|GwGww|
wwwww|GwGGw|
wwGGw|wGwGG|
+—–+
wwGwG wwGwG

解説

範囲内の金山を数えるプログラムを用意しておき、土地の範囲を1つずつ動かして、最大の座標を求めると答えを得られます。

xを0から5まで移動するループと、yを0から5まで移動するループをネストして枠を動かし、その内部の金山の数を数えます。以下、図です。

// {“x”:0,”y”:0} → Gは4
+—–+
|wwGww|wwwGG
|Gwwww|wwwww
|wwwww|wwwww
|Gwwww|wwwww
|wwwwG|wwGww
+—–+
wGwww wwwww
wwwGG wwwww
wwwww wGwww
wwwwG Gwwww
GwwwG GwGwG

// {“x”:1,”y”:0} → Gは2
+—–+
w|wGwww|wwGG
G|wwwww|wwww
w|wwwww|wwww
G|wwwww|wwww
w|wwwGw|wGww
+—–+
w Gwwww wwww
w wwGGw wwww
w wwwww Gwww
w wwwGG wwww
G wwwGG wGwG

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