2
0

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

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

感想

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

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

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0