ABC-045-D すぬけ君の塗り絵

■■■問題■■■

縦H行、横W列のマス目からなる盤があります。最初、どのマス目も白く塗られています。

すぬけ君が、このうちNマスを黒く塗りつぶしました。
i回目 ( 1 <= i <= N ) に塗りつぶしたのは、 上からai行目で左からbi列目のマスでした。

すぬけ君がマス目を塗りつぶした後の盤の状態について、
以下のものの個数を計算してください。
●各整数 j ( 0 <= j <= 9 ) について、
  盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、
  黒いマスがちょうどj個あるもの。

■■■入力■■■

H W N
a1 b1
・
・
・
aN bN

●3 <= H <= 10億
●3 <= W <= 10億
●0 <= N <= min(10万,H×W)
●1 <= ai <= H (1 <= i <= N)
●1 <= bi <= W (1 <= i <= N)
●(ai,bi)≠(aj,bj) (i≠j)

■■■出力■■■

出力は10行からなる。

j+1 行目 ( 0 <= j <= 9 ) には、
盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、
黒いマスがちょうどj個あるものの 総数を出力せよ。

■■■サンプルケースのイメージ■■■

■入出力例1のイメージ■



この盤に含まれる 3×3 の正方形は全部で6個ありますが、
これらのうち2個の内部には黒いマスが3個、
残りの4個の内部には黒いマスが4個含まれています。

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 8");
            WillReturn.Add("1 1");
            WillReturn.Add("1 4");
            WillReturn.Add("1 5");
            WillReturn.Add("2 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 2");
            WillReturn.Add("3 4");
            WillReturn.Add("4 4");
            //0
            //0
            //0
            //2
            //4
            //0
            //0
            //0
            //0
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10 20");
            WillReturn.Add("1 1");
            WillReturn.Add("1 4");
            WillReturn.Add("1 9");
            WillReturn.Add("2 5");
            WillReturn.Add("3 10");
            WillReturn.Add("4 2");
            WillReturn.Add("4 7");
            WillReturn.Add("5 9");
            WillReturn.Add("6 4");
            WillReturn.Add("6 6");
            WillReturn.Add("6 7");
            WillReturn.Add("7 1");
            WillReturn.Add("7 3");
            WillReturn.Add("7 7");
            WillReturn.Add("8 1");
            WillReturn.Add("8 5");
            WillReturn.Add("8 10");
            WillReturn.Add("9 2");
            WillReturn.Add("10 4");
            WillReturn.Add("10 9");
            //4
            //26
            //22
            //10
            //2
            //0
            //0
            //0
            //0
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000 1000000000 0");
            //999999996000000004
            //0
            //0
            //0
            //0
            //0
            //0
            //0
            //0
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

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

        //そのマスを始点としての黒マスの数[座標のHash値]
        var CntDict = new Dictionary<long, long>();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            long a = wkArr[0];
            long b = wkArr[1];

            for (long LoopX = b - 2; LoopX <= b; LoopX++) {
                if (LoopX < 1) continue;
                if (LoopX + 2 > W) break;

                for (long LoopY = a - 2; LoopY <= a; LoopY++) {
                    if (LoopY < 1) continue;
                    if (LoopY + 2 > H) break;

                    long Hash = LoopX * (H + 1) + LoopY;
                    if (CntDict.ContainsKey(Hash))
                        CntDict[Hash]++;
                    else CntDict[Hash] = 1;
                }
            }
        }

        long[] CntArr = new long[10];
        CntArr[0] = (H - 2) * (W - 2);
        foreach (long EachValue in CntDict.Values) {
            CntArr[EachValue]++;
            CntArr[0]--;
        }
        Array.ForEach(CntArr, X => Console.WriteLine(X));
    }
}

解説

塗ったマスごとに、
そのマスを始点としての黒マスの数[座標のHash値]
を更新してます。