[paiza]「島探し」にC#で挑戦しました（paizaランク S相当）

paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」の参加記事になります。

前回のmod7占いで味を占めたので、同じSランク問題の島探しに挑戦してみました。

答案

using System;
using System.Linq;

namespace CountIsle
{
    public class Program
    {
        static void Main(string[] args)
        {
            var dimensions = ReadLineAndGetIntArray();
            var width = dimensions[0];
            var height = dimensions[1];

            var board = new Board(width, height);
            for (var row = 0; row < height; row++)
            {
                var line = ReadLineAndGetIntArray();
                for (var col = 0; col < line.Length; col++)
                {
                    var value = line[col];
                    board.AddCell(col, row, value);
                }
            }

            board.Resolve();

            Console.WriteLine(board.IslesCount);
        }

        private static int[] ReadLineAndGetIntArray()
            => ReadLineAndTrim()
                .Split(' ')
                .Select(str => int.Parse(str))
                .ToArray();

        private static string ReadLineAndTrim() => Console.ReadLine().Trim();
    }

    public class Board
    {
        public int Width { get; }
        public int Height { get; }

        private Cell[,] cells { get; }

        public int IslesCount { get; set; } = 0;

        public Board(int width, int height)
        {
            Width = width;
            Height = height;

            cells = new Cell[height, width];
        }

        public void AddCell(int col, int row, int value) => cells[row, col] = new Cell(col, row, value);

        public void Resolve()
        {
            for (var row = 0; row < Height; row++)
            {
                for (var col = 0; col < Width; col++)
                {
                    var cell = cells[row, col];
                    if (cell.IsSeekerTarget)
                    {
                        Seek(col, row);
                        IslesCount++;
                    }
                }
            }
        }

        private void Seek(int col, int row)
        {
            if (col < 0 || col >= Width || row < 0 || row >= Height) return;
            var cell = cells[row, col];
            if (!cell.IsSeekerTarget) return;

            cell.IsVisited = true;

            Seek(col - 1, row); // 左
            Seek(col + 1, row); // 右
            Seek(col, row - 1); // 上
            Seek(col, row + 1); // 下
        }
    }

    public class Cell
    {
        public int Col { get; }
        public int Row { get; }

        public bool IsBlack { get; }

        public bool IsVisited { get; set; }

        public bool IsSeekerTarget => !IsVisited && IsBlack;

        public Cell(int col, int row, int input)
        {
            Col = col;
            Row = row;
            IsBlack = input == 1;
        }
    }
}

戦略

前回の「mod7占い」と異なり、パフォーマンス的な制約は厳しくないのでクラスを作って可読性をマシに。あと多次元配列 超苦手なので名前つけないと死ぬ。

「島 = 要はつながってる部分全部やろ？」ということで、Boardを先頭から舐めていって、対象のCellが見つかればそこから全探索させるという方針に決定。探査が終われば島カウント++で、まーいけるやろ。

あとは見様見真似で全探索のアルゴリズムをBoard（というかSeekerかな）に実装して、なんとか正答。

方針は割とすぐ定まったが、全探索アルゴリズムの実装が大変だった……マジで配列無理や。

感想

我ながら、この問題をみて全探索を思いつけたのはえらかったです。
まあ調べてみたら、この手の問題は全探索の定番問題みたいですが。

自分はあまりアルゴリズムや競プロ的な領域に明るくないので、見聞の広さと発想力ゥ……ですかね……俺またなんかやっちゃいました？