ぷよぷよを解く

人材募集企画 2011年版: 人生を書き換える者すらいた。 の【問題２】を解いてみました。30 分以上、1 時間未満でした。

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

class Loc {
    public int Row { get; private set; }
    public int Col { get; private set; }
    public Loc(int row, int col) {
        Row = row;
        Col = col;
    }
}

class Puyo {
    static void Display(char[][] g) {
        for (int i = 0; i < g.Length; i++) {
            for (int j = 0; j < g[i].Length; j++) {
                Console.Write(g[i][j]);
            }
            Console.WriteLine();
        }
        Console.WriteLine("------");
    }

    static List<Loc> Group(Loc loc, char[][] g, int[,] used) {
        char puyo = g[loc.Row][loc.Col];
        var group = new List<Loc>();

        int rows = g.Length;
        int cols = g[0].Length;

        var q = new Queue<Loc>();
        q.Enqueue(loc);
        while (q.Count > 0) {
            var p = q.Dequeue();

            // 範囲外
            if (!(0 <= p.Row && p.Row < rows && 0 <= p.Col && p.Col < cols)) continue;
            // ぷよが異なる
            if (puyo != g[p.Row][p.Col]) continue;
            // 探索済み
            if (used[p.Row, p.Col]++ > 0) continue;

            group.Add(p);
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (Math.Abs(i) + Math.Abs(j) == 1) {
                        q.Enqueue(new Loc(p.Row + i, p.Col + j));
                    }
                }
            }
        }
        return group;
    }

    static void Pack(char[][] g) {
        int rows = g.Length;
        int cols = g[0].Length;

        for (int c = 0; c < cols; c++) {
            var xs = new List<char>();
            for (int r = rows-1; r >= 0; r--) {
                if (g[r][c] != ' ') {
                    xs.Add(g[r][c]);
                }
            }
            for (int i = 0; i < rows; i++) {
                g[rows-i-1][c] = i < xs.Count ? xs[i] : ' ';
            }
        }
    }

    static void Solve(char[][] g) {
        int rows = g.Length;
        int cols = g[0].Length;

        bool update = true;
        while (update) {
            update = false;

            int[,] used = new int[rows, cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (g[i][j] == ' ' || used[i, j] > 0) continue;

                    var group = Group(new Loc(i, j), g, used);
                    if (group.Count >= 4) {
                        foreach (Loc loc in group) {
                            g[loc.Row][loc.Col] = ' ';
                        }
                        update = true;
                    }
                }
            }

            if (update) {
                // Console.WriteLine("delete");
                // Display(g);
                Pack(g);
                Display(g);
            }
        }
    }

    static void Main() {
        string[] g = {
            "  GYRR",
            "RYYGYG",
            "GYGYRR",
            "RYGYRG",
            "YGYRYG",
            "GYRYRG",
            "YGYRYR",
            "YGYRYR",
            "YRRGRG",
            "RYGYGG",
            "GRYGYR",
            "GRYGYR",
            "GRYGYR",
        };

        char[][] gg = new char[g.Length][];
        for (int i = 0; i < g.Length; i++) {
            gg[i] = g[i].ToCharArray();
        }
        Solve(gg);
    }
}

• 文字を上書きするために string を char[] に変換しています。

この問題は、Qiita の以下の記事で知りました。