2015年04月05日

C#で島の数をカウントする

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その82

■問題 (出題者:ckbx さん)
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
 

すでに数えた島かどうかを判定するために、違う色で塗りつぶすという方法で島の数をカウントしています。
以下のコードでは、Paintメソッドが塗りつぶすメソッドです。
そのジ上位メソッドで、塗りつぶせれば +1 し、すでに塗りつぶされたならばそのまま、 カウントしたい島とは別の色ならば、そのまま何もしません。
これで、簡単にカウントすることができます。
ちなみに、塗りつぶしは、再帰処理を使っています。

塗りつぶしには、Color.Markというメンバーを定義し、この値で塗りつぶしています。 Colorクラスなのに、Markというのも変ですが...

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] tbl = Data.Table();
            Field sample = new Field(tbl);

            int cnt = sample.Count(Color.White);
            Console.WriteLine("白の島は{0}",cnt);
            int cnt2 = sample.Count(Color.Black);
            Console.WriteLine("黒の島は{0}", cnt2);
        }
    }

    static class Color {
        public const int White = 0;
        public const int Black = 1;
        public const int Mark = 5;
    }
    struct Point {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        private int x;
        private int y;
        public int X { get { return x; } }
        public int Y { get { return y; } }
    }

    public class Field {
        private int[,] table;
        private int width;
        private int height;
        public Field(string[] lines) {
            width = lines[0].Length;
            height = lines.Length;
            table = new int[width, height];
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    table[x, y] = (lines[y][x] == '□') ? Color.White : Color.Black;
                }
            }
            Print();
        }

        public int Count(int color) {
            int count = 0;
            int[,] save = (int[,])table.Clone();
            for (int x = 0; x < width; x++) {
                for (int y = 0; y < height; y++) {
                    if (table[x, y] == color) {
                        Paint(x, y,color);
                        count++;
                    }
                }
            }
            return count;
        }

        // (x,y)とその連続する場所をcolorで塗りつぶす
        private void Paint(int x, int y,int color) {
            table[x, y] = Color.Mark;  // マークを付ける
            foreach (var p in Around(x, y)) {
                if (table[p.X, p.Y] == color)
                    Paint(p.X, p.Y,color);
            }
        }

        private IEnumerable<Point> Around(int x, int y) {
            if (y > 0)
                yield return new Point(x, y - 1);
            if (y < height - 1)
                yield return new Point(x, y + 1);
            if (x > 0)
                yield return new Point(x - 1, y);
            if (x < width - 1)
                yield return new Point(x + 1, y);
        }

        // デバッグ用
        private void Print() {
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++)
                    Console.Write(table[x, y]);
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }

    public static class Data {
        public static string[] Table() {
            return File.ReadAllLines("Islands.txt");
        }
    }
}

以下のファイルを読み込ませれば、

白の島は3
黒の島は4

と表示されます。

■読み込ませるファイルの内容
□□■□□□
□■■□■■
□□■■□□
□□□□■□
□□■□■■
□■■□□□
□■□□□□


 

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

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