AGC-007-A Shik and Stone

■■■問題■■■

縦H行、横W列のマス目に区切られた盤面があります。

はじめ、駒が左上隅のマスに置かれていました。
シックはこの駒を1マスずつ上下左右に動かし、右下隅のマスに移動させました。
このとき、駒が同じマスを複数回通った可能性もあります(左上隅や右下隅のマスも含む)。

縦横に並んだ文字 aij (1 <= i <= H, 1 <= j <= W) が与えられます。

aij が # のとき、駒が移動する過程でi行j列目のマスを一度以上通ったことを表します
(左上隅や右下隅のマスは必ず通ったものとして扱います)。
aijが.のとき、駒がi行j列目のマスを一度も通らなかったことを表します。

移動する過程で、駒が常に右または下に動いていた可能性があるか判定してください。

■■■入力■■■

H W
A11A12・・・A1W
・
・
・
AH1AH2・・・AHW

●2 <= H,W <= 8
●aij は#または.である。
●問題文およびaで与えられる情報と整合するような駒の動き方が存在する。

■■■出力■■■

移動する過程で、駒が常に右または下に動いていた可能性があればPossible、
なければImpossibleと出力せよ。

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("4 5");
            WillReturn.Add("##...");
            WillReturn.Add(".##..");
            WillReturn.Add("..##.");
            WillReturn.Add("...##");
            //Possible
            //右、下、右、下、右、下、右と駒が動くと、
            //通るマスが与えられた情報と合致します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 3");
            WillReturn.Add("###");
            WillReturn.Add("..#");
            WillReturn.Add("###");
            WillReturn.Add("#..");
            WillReturn.Add("###");
            //Impossible
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 5");
            WillReturn.Add("##...");
            WillReturn.Add(".###.");
            WillReturn.Add(".###.");
            WillReturn.Add("...##");
            //Impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int H = wkArr[0], W = wkArr[1];
        int UB_X = W - 1, UB_Y = H - 1;

        char[,] BanArr = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                BanArr[X, Y] = InputList[Y + 1][X];
            }
        }
        int SharpCnt = BanArr.Cast<char>().Count(A => A == '#');

        int CurrX = 0, CurrY = 0;
        bool[,] IsVisitedArr = new bool[UB_X + 1, UB_Y + 1];

        while (true) {
            IsVisitedArr[CurrX, CurrY] = true;

            //クリア判定
            if (CurrX == UB_X && CurrY == UB_Y) {
                if (IsVisitedArr.Cast<bool>().Count(A => A) == SharpCnt) {
                    Console.WriteLine("Possible");
                }
                else Console.WriteLine("Impossible");
                return;
            }

            bool CanMoveShita = false; //下に移動可能か？
            bool CanMoveMigi = false; //右に移動可能か？

            if (CurrY < UB_Y && BanArr[CurrX, CurrY + 1] == '#') CanMoveShita = true;
            if (CurrX < UB_X && BanArr[CurrX + 1, CurrY] == '#') CanMoveMigi = true;

            if (CanMoveShita && CanMoveMigi) {
                break;
            }
            else if (CanMoveShita) {
                CurrY++; continue;
            }
            else if (CanMoveMigi) {
                CurrX++; continue;
            }
            else break;
        }
        Console.WriteLine("Impossible");
    }
}

解説

●右と下の両方に移動可能なら、Impossible。
●右のみに移動可能ならば、右に移動する。
●下のみに移動可能ならば、下に移動する。
●右も下も移動不可なら、Impossible。
という処理の繰り返しで、ゴールに到着した際に、全部の#に訪問したかを判定してます。