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

[paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」](https://qiita.com/official-events/9ab96aa95d62fe3cbdd7)の参加記事になります。

前回の[mod7占い](https://qiita.com/mia106/items/46c328d54acf3d63c2fb)で味を占めたので、同じSランク問題の[島探し](https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island)に挑戦してみました。

## 答案

```cs
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かな）に実装して、なんとか正答。

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

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

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