×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

最大面積の領域を求める

問題

下のように、黒と白からなる配列があります。

○○○○●●●●●○
○○●●●●●●○●
○○●●●●○●●●
●●●●●●●●●○
●●○○○●○●●●
●●○○●●○●●●
●●○○●●○●●○

この中で、最大となる黒の正方形の面積を求めてください。
上の例では、9が最大の面積となります。


※マップの上でマウスをドラッグさせるとその範囲が黒になります。黒部分を変更して動きを確かめてください。

すべての地点に対し、その地点を正方形の左上としたしたときの面積を求め、一番大きなのがどれかを求めています。

どうやって正方形かどうかを判断するかですが、
例えば、以下の図で、△部分が黒の正方形であると分かっている場合を考えます。

△△△△☆
△△△△☆
△△△△☆
△△△△☆
★★★★●

△部分の右下を(x,y)地点とすると、
(1) (x+1,y+1) が黒
(2) ☆部分がすべて黒
(3) ★部分がすべて黒
を満たした場合、正方形の辺の長さは + 1 となり、△部分が増えることになります。
これを繰り返していけば、正方形の辺の長さが求まることになります。

再帰処理の応用としてとらえることができますね。

なお、面積が最大の長方形も求められるようにしています。こちらは正方形よりも泥臭い方法で最大面積を求めています。まず、注目している点が長方形の左上とした時の、高さが1の長方形の面積を求めます。次に高さが2の長方形の面積を求めます。高さが3,4,5... と求めていき、最大の長方形を求めます。これをすべての点で実行しています。

以下に、コードを示しますが、マウスのドラッグ操作の機能を入れたり、求めた領域を赤で囲む機能をいれたりで、MainPage.xaml.csのコードが、思いのほか長くなってしまいました。
問題を解く本質部分は、MaxAreaProblem.csが担当していますので、問題を解くロジックに興味があるかたは、MaxAreaProblem.csだけを読んでください。

※このプログラムは、そのほかのプログラムでも利用する Board, BoardCanvasクラスを利用しています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

■MaxAreaProblem.cs


■MainPage.xaml.cs

 
■MainPage.xaml
 

※『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。