ABC-069-D Grid Coloring

■■■問題■■■

縦H行、横W列のマス目があります。
すぬけ君は、このマス目を色 1, 2, ・・・ , N で塗り分けようとしています。
このとき、次の条件が成り立つようにします。

●各i (1 <= i <= N) について、色iのマスはちょうどai個存在する。
  ただし、a1 + a2 + ・・・ + aN = HW である。
●各i (1 <= i <= N) について、色iのマスは上下左右に連結である。
  すなわち、どの色iのマスからどの色iのマスへも、上下左右に隣り合う色iのマスのみを辿って行き来できる。

条件を満たす塗り分け方をひとつ求めてください。解は必ず存在することが示せます。

■■■入力■■■

H W
N
a1 a2 ・・・ aN

●1 <= H,W <= 100
●1 <= N <= HW
●ai >= 1
●a1 + a2 + ・・・ + aN = HW

■■■出力■■■

条件を満たす塗り分け方をひとつ出力せよ。塗り分け方は次のフォーマットで出力せよ。
ただし、cijは、上からi行目、左からj列目のマスの色である。

c11 ・・・ c1W
・
・
・
cH1 ・・・ cHW

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2 2");
            WillReturn.Add("3");
            WillReturn.Add("2 1 1");
            //1 1
            //2 3
            //例えば、次の塗り分け方は条件を満たしません。
            //色1のマスが上下左右に連結でないからです。
            //1 2
            //3 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 5");
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5");
            //1 4 4 4 3
            //2 5 4 5 3
            //2 5 5 5 3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //1
        }
        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];
        int W = wkArr[1];

        int[] AArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray();

        int UB_X = W - 1;
        int UB_Y = H - 1;

        int[,] BanArr = new int[UB_X + 1, UB_Y + 1];
        int CurrInd = 0;

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                int TargetX = X;
                if (Y % 2 == 1) TargetX = UB_X - X;

                BanArr[TargetX, Y] = CurrInd + 1;
                AArr[CurrInd]--;
                if (AArr[CurrInd] == 0) {
                    CurrInd++;
                }
            }
        }

        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(BanArr[X, Y]);
                if (X < UB_X) sb.Append(" ");
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

解説

下記のように
蛇のような動きで、マス目を埋めれば、
必ず各色を連結させることができます。

123
654
789