ABC232-E Rook Path

問題へのリンク

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 2 2");
            WillReturn.Add("1 2 2 1");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000000000 1000000000 1000000");
            WillReturn.Add("1000000000 1000000000 1000000000 1000000000");
            //24922282
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 3 3");
            WillReturn.Add("1 3 3 3");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long H = wkArr[0];
        long W = wkArr[1];
        long MoveCnt = wkArr[2];

        SplitAct(InputList[1]);
        long X1 = wkArr[1];
        long Y1 = wkArr[0];
        long X2 = wkArr[3];
        long Y2 = wkArr[2];

        // 場合の数[X座標がゴールか？ , Y座標がゴールか？]なDP表
        long[,] PrevDP = new long[2, 2];

        long StaX = 0;
        long StaY = 0;
        if (X1 == X2) StaX = 1;
        if (Y1 == Y2) StaY = 1;
        PrevDP[StaX, StaY] = 1;

        for (long I = 1; I <= MoveCnt; I++) {
            long[,] CurrDP = new long[2, 2];
            for (long J = 0; J <= 1; J++) {
                for (long K = 0; K <= 1; K++) {
                    if (PrevDP[J, K] == 0) continue;
                    long CurrCnt = PrevDP[J, K];

                    Action<long, long, long> AddAct = (pNewJ, pNewK, pPatternCnt) =>
                    {
                        pPatternCnt %= Hou;
                        CurrDP[pNewJ, pNewK] += pPatternCnt;
                        CurrDP[pNewJ, pNewK] %= Hou;
                    };

                    if (J == 0 && K == 0) {
                        long AddPattern = (W - 2) + (H - 2);
                        AddAct(0, 0, CurrCnt * AddPattern);
                        AddAct(0, 1, CurrCnt);
                        AddAct(1, 0, CurrCnt);
                    }

                    if (J == 0 && K == 1) { // X座標はゴールでなく、Y座標はゴールの場合
                        AddAct(0, 0, CurrCnt * (H - 1));
                        AddAct(0, 1, CurrCnt * (W - 2));
                        AddAct(1, 1, CurrCnt);
                    }
                    if (J == 1 && K == 0) { // X座標はゴールで、Y座標はゴールでない場合
                        AddAct(0, 0, CurrCnt * (W - 1));
                        AddAct(1, 0, CurrCnt * (H - 2));
                        AddAct(1, 1, CurrCnt);
                    }

                    if (J == 1 && K == 1) {
                        AddAct(0, 1, CurrCnt * (W - 1));
                        AddAct(1, 0, CurrCnt * (H - 1));
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[1, 1]);
    }
}

解説

場合の数[X座標 , Y座標] だとTLEするので
場合の数[X座標がゴールか？ , Y座標がゴールか？] でDPしてます。