ARC-021-A DEAD END

■■■問題■■■

あなたは友人の高橋君からとあるゲームを熱烈にオススメされている。

このゲームは4×4のグリッド状に区切られた16個のセルと、
その上に置かれた数が書かれたタイルを使ってプレーする。

1回の操作では上下左右の4方向のうちいずれかを指定することができ、
指定した方向に向かってセル上のタイルが滑っていく。

このとき、同じ数の書かれたタイル2枚がぶつかるとその2枚はグリッド上から取り除かれ、
代わりに数を2倍した別のタイルが1枚新たに置かれる。

次の図は盤面の状態と、そこから右に向かって1回操作を行った後の盤面の例である。



上下左右のどの方向を指定してもタイルがまったく滑ることができず、
同じ数のタイルをぶつけることもできなくなったらゲームオーバーで、
それまでに出来るだけ大きい数の書かれたタイルを作るのが目的だ。

このゲームは確かに非常に面白そうだと思ったが、まだ慣れていないからか、
グリッド上がタイルでいっぱいになったときにゲームオーバーなのかをなかなか判別できない。
そこで、グリッド上のタイルの情報が与えられたときに
ゲームオーバーの状態なのかどうかを判定するようなプログラムを書くことにした。

■■■入力■■■

A1,1 A1,2 A1,3 A1,4
A2,1 A2,2 A2,3 A2,4
A3,1 A3,2 A3,3 A3,4
A4,1 A4,2 A4,3 A4,4

●4行にわたってタイルの情報が書かれている。
  Ar,c (2 <= Ar,c <= 2048) は、グリッド上で
  上から数えてr番目、左から数えてc番目の
  セルに置かれているタイルに書かれている数を表す。 

●Ar,cはすべて2の累乗である。
  すなわち、Ar,cは2,4,8,16,32,64,128,256,512,1024,2048のいずれかである。

■■■出力■■■

与えられたグリッドの状態がゲームオーバーならGAMEOVER、
まだ操作ができるならCONTINUEと1行に出力せよ。
出力の末尾にも改行をいれること。

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 8 2 2");
            WillReturn.Add("32 2 8 8");
            WillReturn.Add("4 64 2 128");
            WillReturn.Add("2 8 4 2");
            //CONTINUE
            //上下にはタイルを動かすことができませんが、
            //左右に動かせば2が書かれたタイルどうしや
            //8が書かれたタイルどうしをぶつけることが可能です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 4 16 4");
            WillReturn.Add("8 32 128 8");
            WillReturn.Add("2 64 16 2");
            WillReturn.Add("32 4 32 4");
            //GAMEOVER
            //どの方向に動かそうとしても
            //同じ数の書かれたタイルをぶつけることができません。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 4 2 4");
            WillReturn.Add("4 2 4 2");
            WillReturn.Add("2 4 2 4");
            WillReturn.Add("4 2 4 2");
            //GAMEOVER
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int UB = 3;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[,] AArr = new int[UB + 1, UB + 1];

        for (int Y = 0; Y <= UB; Y++) {
            int[] wkArr = InputList[Y].Split(' ').Select(X => int.Parse(X)).ToArray();
            for (int X = 0; X <= UB; X++) {
                AArr[X, Y] = wkArr[X];
            }
        }

        bool IsExistSameNum = false;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (ExistSameNum(AArr, X, Y))
                    IsExistSameNum = true;
            }
        }
        Console.WriteLine(IsExistSameNum ? "CONTINUE" : "GAMEOVER");
    }

    //4近傍に同じ数値があるかを返す
    static bool ExistSameNum(int[,] pAArr, int pCurrX, int pCurrY)
    {
        Func<int, int, bool> wkFunc = (pNewX, pNewY) =>
        {
            if (pNewX < 0 || UB < pNewX) return false;
            if (pNewY < 0 || UB < pNewY) return false;

            return pAArr[pNewX, pNewY] == pAArr[pCurrX, pCurrY];
        };

        if (wkFunc(pCurrX, pCurrY - 1)) return true;
        if (wkFunc(pCurrX, pCurrY + 1)) return true;
        if (wkFunc(pCurrX - 1, pCurrY)) return true;
        if (wkFunc(pCurrX + 1, pCurrY)) return true;
        return false;
    }
}

解説

4近傍に同じ数値があるかをチェックしてます。