ABC-039-D 画像処理高橋君

■■■問題■■■

2値画像に対して行う、収縮という処理があります。
なお、2値画像とは、画素の色が白か黒かの2種類しかない画像の事です。

収縮とは、それぞれの画素についてその画素と周り8方向の画素のうち、
一つでも黒い画素があったらその画素を黒くするという処理です。

ここで、画素数が高さH、幅Wの2値画像を考えます。
この画像はある画像に一回収縮を行ったものであることがわかっています。
元の画像として考えられるものがあるかを判定し、
もしあるならばそのうちどれか1つを復元してください。

画像は、H個の、W文字の文字列Siで与えられます。
Siのj文字目は、上からi個目、左からj個目の画素の色を表しており、
'.' なら白、'#' なら黒です。

■■■入力■■■

H W
S1
S2
・
・
・
SH

●1 <= H,W <= 100
●SiはW文字の '.'、'#' からなる文字列である

■■■出力■■■

もし条件を満たす画像が無いならば1行に'impossible'と出力する。

条件を満たす画像があるならば1行に'possible'と出力したあと、
W文字の '.'、'#' からなる文字列をH行出力する。
i行目の文字列のj番目の文字は、
条件を満たす画像の上からi個目、左からj個目の画素の色が白なら '.'、黒なら '#' とすること。

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 4");
            WillReturn.Add("##..");
            WillReturn.Add("##..");
            WillReturn.Add("..##");
            WillReturn.Add("..##");
            //possible
            //#...
            //....
            //....
            //...#
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4");
            WillReturn.Add("###.");
            WillReturn.Add("####");
            WillReturn.Add("..##");
            WillReturn.Add("..##");
            //possible
            //##..
            //....
            //...#
            //...#
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4");
            WillReturn.Add("###.");
            WillReturn.Add("##.#");
            WillReturn.Add("..##");
            WillReturn.Add("..##");
            //impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB_X;
    static int UB_Y;

    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];
        char[,] InputBanArr = new char[W, H];
        UB_X = W - 1;
        UB_Y = H - 1;

        for (int Y = 1; Y <= InputList.Count - 1; Y++) {
            for (int X = 0; X <= InputList[Y].Length - 1; X++) {
                InputBanArr[X, Y - 1] = InputList[Y][X];
            }
        }
        //Console.WriteLine(BanToStr(InputBanArr));

        //必要条件で絞込み
        //収縮後で8近傍が全て黒のマスは、収縮前で黒マスであること
        char[,] AnswerBanArr = new char[W, H];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (Is8KinbouAllBlack(InputBanArr, X, Y))
                    AnswerBanArr[X, Y] = '#';
                else AnswerBanArr[X, Y] = '.';
            }
        }

        //十分性のチェック
        //収縮前の画像に、収縮処理をして、収縮後の画像になること
        char[,] AfterBanArr = new char[W, H];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (Is8KinbouAnyBlack(AnswerBanArr, X, Y))
                    AfterBanArr[X, Y] = '#';
                else AfterBanArr[X, Y] = '.';
            }
        }

        if (InputBanArr.Cast<char>().SequenceEqual(AfterBanArr.Cast<char>())) {
            Console.WriteLine("possible");
            Console.Write(BanToStr(AnswerBanArr));
        }
        else Console.WriteLine("impossible");
    }

    //そのマスと、8近傍が、全て黒かを判定
    static bool Is8KinbouAllBlack(char[,] pBanArr, int pX, int pY)
    {
        Func<int, int, bool> wkFunc = (pTargetX, pTargetY) =>
        {
            if (pTargetX < 0 || UB_X < pTargetX) return true;
            if (pTargetY < 0 || UB_Y < pTargetY) return true;
            return pBanArr[pTargetX, pTargetY] == '#';
        };

        for (int HeniX = -1; HeniX <= 1; HeniX++)
            for (int HeniY = -1; HeniY <= 1; HeniY++)
                if (wkFunc(pX + HeniX, pY + HeniY) == false) return false;
        return true;
    }

    //そのマスと、8近傍の、少なくとも1つが黒かを判定
    static bool Is8KinbouAnyBlack(char[,] pBanArr, int pX, int pY)
    {
        Func<int, int, bool> wkFunc = (pTargetX, pTargetY) =>
        {
            if (pTargetX < 0 || UB_X < pTargetX) return false;
            if (pTargetY < 0 || UB_Y < pTargetY) return false;
            return pBanArr[pTargetX, pTargetY] == '#';
        };

        for (int HeniX = -1; HeniX <= 1; HeniX++)
            for (int HeniY = -1; HeniY <= 1; HeniY++)
                if (wkFunc(pX + HeniX, pY + HeniY)) return true;
        return false;
    }

    static string BanToStr(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}

解説

まず下記の必要条件で絞込みしてます。
収縮後で8近傍が全て黒のマスは、収縮前で黒マスであること

次に、十分性のチェックとして、
収縮前の画像に、収縮処理をして、収縮後の画像になるかを見てます。