■某ブログの問題を解いてみた

http://okajima.air-nifty.com/b/2011/01/2011-ffac.html

ぷよぷよを解く問題をやってみた

かかった時間はおおよそ１時間半

途中でわからないところがあったのでくぐってしまった

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder[] blocks = {
                new StringBuilder("**GYRR"),
                new StringBuilder("RYYGYG"),
                new StringBuilder("GYGYRR"),
                new StringBuilder("RYGYRG"),
                new StringBuilder("YGYRYG"),
                new StringBuilder("GYRYRG"),
                new StringBuilder("YGYRYR"),
                new StringBuilder("YGYRYR"),
                new StringBuilder("YRRGRG"),
                new StringBuilder("RYGYGG"),
                new StringBuilder("GRYGYR"),
                new StringBuilder("GRYGYR"),
                new StringBuilder("GRYGYR")
            };

            bool updated = true;
            while (updated)
            {
            breaked:
                DumpBlock(blocks);
                for (int i = 0; i < blocks.Length; i++)
                {
                    for (int j = 0; j < blocks[i].Length; j++)
                    {
                        char c = blocks[i][j];
                        if (c == '*')
                            continue;
                        updated = false;
                        if (KillBlocks(blocks, i, j))
                        {
                            updated = true;
                            goto breaked;
                        }
                    }
                }
            }
            DumpBlock(blocks);
            Console.Read();
        }
        struct Point
        {
            public int x, y;
            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }
        static bool KillBlocks(StringBuilder[] blocks, int x, int y)
        {
            bool[,] visted = new bool[blocks.Length,blocks[0].Length];

            MarkBlock(visted, blocks, x, y);

            Queue<Point> queque = new Queue<Point>();
            for (int i = x; i < blocks.Length; i++)
                for (int j = y; j < blocks[i].Length; j++)
                    if(visted[i,j] == true)
                        queque.Enqueue(new Point(j,i));

            if (queque.Count < 4)
                return false;

            while (queque.Count > 0)
            {
                Point p = queque.Dequeue();
                RemoveBlock(blocks, p.x, p.y);
            }
            return true;
        }
        static void MarkBlock(bool[,] visted, StringBuilder[] blocks, int x, int y)
        {
            if (x < 0 || y < 0 || x >= blocks.Length || y >= blocks[0].Length || visted[x, y] == true)
                return;
            char c = blocks[x][y];
            visted[x, y] = true;
            if (x + 1 < blocks.Length && blocks[x + 1][y] == c) MarkBlock(visted, blocks, x + 1, y);
            if (y + 1 < blocks[0].Length && blocks[x][y + 1] == c) MarkBlock(visted, blocks, x, y + 1);
            if (x > 0 && blocks[x - 1][y] == c) MarkBlock(visted, blocks, x - 1, y);
            if (y > 0 && blocks[x][y - 1] == c) MarkBlock(visted, blocks, x, y - 1);
        }
        static void DumpBlock(StringBuilder[] blocks)
        {
            foreach (StringBuilder s in blocks)
                Console.WriteLine(s);
            Console.WriteLine();
        }
        static void RemoveBlock(StringBuilder[] blocks,int x,int y)
        {
            int i;
            if (y == 0)
            {
                blocks[y][x] = '*';
                return;
            }
            for (i = y; i > 0; i--)
            {
                blocks[i][x] = blocks[i - 1][x];
            }
            blocks[i][x] = '*';
        }
    }
}

Permalink | 記事への反応(1) | 22:53

ツイートシェア