takeaki_o さん、Sirokuroさんが取り組んでるマインスイーパのアルゴリズムに僕も挑戦してみました。
takeaki_oさんのエントリ
Sirokuroさんのエントリ
Sirokuroさんのアルゴリズムは再帰を使っていますので、僕は再帰を使わない方針でチャレンジしてみました。
05/07/04 11:04 修正 toOpen2.Add(... の行の括弧の対応がおかしかったorz
// マインスイーパのセルを開くアルゴリズム (再帰なしのバージョン)
class Mine{
// -1 : 爆弾, 0以上 : 周辺の爆弾の数
int[,] cells = new int[5,5];
// 既に開いてたら true, まだなら false
bool[,] isOpened = new bool[5,5];
// cells の指定された座標の値が0でかつまだ開いてなかったら true、それ以外は false
bool CheckIfZeroAndNotOpenedYet(int x, int y){
// 盤面外ならfalse
if (x < 0 || x >= 5 || y < 0 || y >= 5) return false;
if (cells[x,y] == 0 && isOpened[x,y] == false) return true;
else false;
// ↑の2行をもっと短く書くとしたら・・・
// return ((cells[x,y] == 0) && !isOpened[x,y]);
}
// (x,y) の座標のマスを開く。0なら周囲のマスも開く
void OpenCells(int x, int y){
// まず自分の座標を調べる
if (!CheckIfZeroAndNotOpenedYet(x,y)) return;
isOpened[x,y] = true;
// このターンのループで開く座標
ArrayList toOpen = new ArrayList();
toOpen.Add(new Point(x,y));
while(toOpen.Count > 0){
// 次のループでチェックする座標を入れていく
ArrayList toOpen2 = new ArrayList();
foreach(Point p in toOpen){
if (p.X < 0 || p.Y >= 5 || p.Y < 0 || p.Y >= 5) continue;
if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y-1)){ // 左上
toOpen2.Add(new Point(p.X-1,p.Y-1));
}
if (CheckIfZeroAndNotOpenedYet(p.X,p.Y-1)){ // 上
toOpen2.Add(new Point(p.X,p.Y-1));
}
if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y-1)){ // 右上
toOpen2.Add(new Point(p.X+1,p.Y-1));
}
if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y)){ // 左
toOpen2.Add(new Point(p.X-1,p.Y));
}
if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y)){ // 右
toOpen2.Add(new Point(p.X+1,p.Y));
}
if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y+1)){ // 左下
toOpen2.Add(new Point(p.X-1,p.Y+1));
}
if (CheckIfZeroAndNotOpenedYet(p.X,p.Y+1)){ // 下
toOpen2.Add(new Point(p.X,p.Y+1));
}
if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y+1)){ // 右下
toOpen2.Add(new Point(p.X+1,p.Y+1));
}
}
// 新たに開いたところの isOpened を true にする
foreach(Point p in toOpen2){
isOpened[p.X,p.Y] = true;
}
toOpen = toOpen2;
}
}
// その他もろもろの処理
}
変数 toOpen, toOpen2 が、takeaki_oさんの説明している変数 checked に近い役割を果たしているように見えますがいかがでしょうか。あとはOpenCellsの最初のほうに爆弾に触ったときの処理を加えたり、CheckIfZeroAndNotOpenedYetに0じゃなかったときの処理を加えたり、必要に応じて戻り値を設定すれば完成すると思います。
(0じゃないときの処理のことも考えると、isOpened[x,y]=trueもCheckIfZeroAndNotOpenedYetに入れちゃったほうがいいかもしれません)
ちなみに、再帰を使うと深さ優先(左上を開けるだけ開いて、次に上を開けるだけ開いて・・・)になって、再帰を使わないと幅優先(近いセルから順番に開いていく)になるかと思います。