2009年04月05日

[パズル]面積最大の領域

  
問題

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

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

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

----------------------------
厳密にはパズルとは言えませんが、プログラミングにおける頭の体操としてはなかなか良い問題だと思います。

データとしては、0を白、1を黒として表現することにします。
すべての地点に対し、その地点を正方形の左上としたしたときの面積を求め、一番大きなのがどれかを求めることとします。
では、どうやって正方形かどうかを判断するかですが、これも再帰処理の応用としてとらえることができます。

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

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

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

C#で書いたコードを示します。今回も LINQ使ってます。

using System;
using System.Linq;

namespace MaxSize {
class Program {
static void Main(string[] args) {
int[,] mat = new int[,] {
{1,0,0,0,1,1,1,1,1,0},
{0,0,1,1,1,1,1,1,0,1},
{0,0,1,1,1,1,0,1,1,1},
{1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,0,1,1,1},
{1,1,1,0,1,1,0,1,1,1},
{1,1,0,0,1,1,0,1,1,1},
};
Solver solver = new Solver();
int n = solver.Solve(mat);
Console.WriteLine(n*n);
}
}

class Solver {
public int Solve(int[,] mat) {
Board board = new Board(mat);
// すべての地点での正方形の辺の長さを求め、その最大値を返す。
return (from x in Enumerable.Range(0, board.XSize)
from y in Enumerable.Range(0, board.YSize)
select new { x, y }
).Max(o => board.GetAreaSize(o.x, o.y));
}
}

class Board {
private int[,] mat;

public int XSize {
get { return mat.GetLength(0); }
}

public int YSize {
get { return mat.GetLength(1); }
}

public Board(int[,] mat) {
this.mat = mat;
}

public int this[int x, int y] {
get { return mat[x, y]; }
}

public int GetYCount(int x, int y) {
return Enumerable.Range(0, y + 1).Reverse()
.TakeWhile(n => mat[x, n] == 1)
.Count();
}

public int GetXCount(int x, int y) {
return Enumerable.Range(0, x + 1).Reverse()
.TakeWhile(n => mat[n, y] == 1)
.Count();
}

public int GetAreaSize(int x, int y) {
return GetAreaSize(x, y, 0);
}

public int GetAreaSize(int x, int y, int width) {
// インデックスオーバーしないようにチェックする
if (x >= mat.GetLength(0))
return width;
if (y >= mat.GetLength(0))
return width;
// 黒じゃなければ、今まで求めたwidthが、正方形の辺の長さ
if (mat[x, y] == 0)
return width;
// X方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
int xc = GetXCount(x, y);
if (xc < width + 1)
return width;
// Y方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
if (GetYCount(x, y) < width + 1)
return width;
// width+1の可能性があるので、右下まで広げて調べる(再帰処理)
return GetAreaSize(x + 1, y + 1, width + 1);
}
}

}




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


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51790409