11-18 島の数をカウントする

問題

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

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

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

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

ソース

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    internal struct NodeDefine
    {
        internal string color;
        internal int X;
        internal int Y;
    }
    static void Main()
    {
        //string[,] SimaMap = {{ "□", "■", "■", "□" },
        //                     { "□", "□", "■", "□" },
        //                     { "□", "■", "□", "□" },
        //                     { "□", "■", "■", "□" }};

        string[,] SimaMap = {{ "□", "□", "□", "□" },
                             { "■", "□", "■", "□" },
                             { "□", "■", "□", "□" },
                             { "□", "□", "□", "□" }};

        var canMoveList = new List<String>();

        for (int X = 0; X <= SimaMap.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= SimaMap.GetUpperBound(1); Y++) {
                var canMove = new List<NodeDefine>();

                var stk = new Stack<NodeDefine>();
                NodeDefine willPush; willPush.color = SimaMap[X, Y]; willPush.X = X; willPush.Y = Y;
                stk.Push(willPush);

                while (stk.Count != 0) {
                    NodeDefine wk = stk.Pop();
                    canMove.Add(wk);

                    if (wk.X >= 1 && SimaMap[wk.X - 1, wk.Y] == wk.color) {
                        willPush.color = wk.color; willPush.X = wk.X - 1; willPush.Y = wk.Y;
                        if (canMove.Contains(willPush) == false) stk.Push(willPush);
                    }
                    if (wk.X <= 2 && SimaMap[wk.X + 1, wk.Y] == wk.color) {
                        willPush.color = wk.color; willPush.X = wk.X + 1; willPush.Y = wk.Y;
                        if (canMove.Contains(willPush) == false) stk.Push(willPush);
                    }
                    if (wk.Y >= 1 && SimaMap[wk.X, wk.Y - 1] == wk.color) {
                        willPush.color = wk.color; willPush.X = wk.X; willPush.Y = wk.Y - 1;
                        if (canMove.Contains(willPush) == false) stk.Push(willPush);
                    }
                    if (wk.Y <= 2 && SimaMap[wk.X, wk.Y + 1] == wk.color) {
                        willPush.color = wk.color; willPush.X = wk.X; willPush.Y = wk.Y + 1;
                        if (canMove.Contains(willPush) == false) stk.Push(willPush);
                    }
                }
                string willAdd = "";
                foreach (var eachVal in canMove.Distinct().OrderBy(ins => ins.X).ThenBy(ins => ins.Y)) {
                    willAdd += eachVal.color;
                    willAdd += eachVal.X + "," + eachVal.Y;
                    willAdd += "->";

                }
                canMoveList.Add(willAdd);
            }
        }
        Console.WriteLine("白の島は" + canMoveList.Where(X => X.StartsWith("□")).Distinct().Count() + "つ");
        Console.WriteLine("黒の島は" + canMoveList.Where(X => X.StartsWith("■")).Distinct().Count() + "つ");
    }
}

実行結果

白の島は1つ
黒の島は3つ

解説

深さ優先探索で移動可能な島を列挙してます。