トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ATC-001-A 深さ優先探索

■■■問題■■■

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。
長方形の各辺は東西及び南北に並行です。
各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。
また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

■■■入力■■■

H W
c0,0 c0,1 c0,W-1
c1,0 c1,1 c1,W-1
・・・
cH-1,0 cH-1,1 cH-1,W-1

●1行目には、街の南北の長さとして整数H(1 <= H <= 500)と
  東西の長さとして整数W(1 <= W <= 500)が空白で区切られて与えられる。

●2行目からのH行には、格子状の街の各区画における状態 ci,j(0 <= i <= H-1,0 <= j <= W-1) が与えられる。
    i行目j文字目の文字 ci,j はそれぞれ sg.# のいずれかで与えられ、
    座標 (j,i) が下記のような状態であることを表す。
        ●'s' : その区画が家であることを表す。
        ●'g' : その区画が魚屋であることを表す。
        ●'.' : その区画が道であることを表す。
        ●'#' : その区画が塀であることを表す。
    ●高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
    ●与えられた街の外を通ることはできない。
    ●sとgはそれぞれ1つずつ与えられる。

■■■出力■■■

塀を1回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、
辿りつけない場合はNoを標準出力に1行で出力せよ。


C#のソース

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

class Program
{
    static string InputPattern = "Input4";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5");
            WillReturn.Add("s####");
            WillReturn.Add("....#");
            WillReturn.Add("#####");
            WillReturn.Add("#...g");
            //No
            //高橋君は、魚屋にたどり着くことができません
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4");
            WillReturn.Add("...s");
            WillReturn.Add("....");
            WillReturn.Add("....");
            WillReturn.Add(".g..");
            //Yes
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 10");
            WillReturn.Add("s.........");
            WillReturn.Add("#########.");
            WillReturn.Add("#.......#.");
            WillReturn.Add("#..####.#.");
            WillReturn.Add("##....#.#.");
            WillReturn.Add("#####.#.#.");
            WillReturn.Add("g.#.#.#.#.");
            WillReturn.Add("#.#.#.#.#.");
            WillReturn.Add("###.#.#.#.");
            WillReturn.Add("#.....#...");
            //No
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 10");
            WillReturn.Add("s.........");
            WillReturn.Add("#########.");
            WillReturn.Add("#.......#.");
            WillReturn.Add("#..####.#.");
            WillReturn.Add("##....#.#.");
            WillReturn.Add("#####.#.#.");
            WillReturn.Add("g.#.#.#.#.");
            WillReturn.Add("#.#.#.#.#.");
            WillReturn.Add("#.#.#.#.#.");
            WillReturn.Add("#.....#...");
            //Yes
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("1 10");
            WillReturn.Add("s..####..g");
            //No
        }
        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();

        InputList.RemoveAt(0);
        UB_X = InputList[0].Length - 1;
        UB_Y = InputList.Count - 1;

        char[,] BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                BanArr[X, Y] = InputList[Y][X];
            }
        }
        PrintBan(BanArr);

        bool HasAnswer = ExecDES(BanArr);
        Console.WriteLine(HasAnswer ? "Yes" : "No");
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal string Path;
    }

    //深さ優先探索を行い解の有無を返す
    static bool ExecDES(char[,] pBanArr)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        var VisitedSet = new HashSet<string>();

        //Sの座標を取得
        int StaX = -1, StaY = -1;

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] == 's') {
                    StaX = X; StaY = Y;
                }
            }
        }

        WillPush.CurrX = StaX;
        WillPush.CurrY = StaY;
        string VisitStr1 = string.Format("({0},{1})", StaX, StaY);
        WillPush.Path = VisitStr1;
        VisitedSet.Add(VisitStr1);
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (pBanArr[Popped.CurrX, Popped.CurrY] == 'g') {
                Console.WriteLine("解を発見");
                Console.WriteLine(Popped.Path);
                return true;
            }

            //Push処理
            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                //塀なら訪問不可
                if (pBanArr[pNewX, pNewY] == '#') return;

                //再訪不可
                string VisitStr2 = string.Format("({0},{1})", pNewX, pNewY);
                if (VisitedSet.Add(VisitStr2) == false) return;

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.Path = Popped.Path + VisitStr2;
                stk.Push(WillPush);
            };
            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }

        return false;
    }

    //盤面を出力
    static void PrintBan(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();
        }
        Console.WriteLine(sb.ToString());
    }
}


デバッグ情報付の実行結果

s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

解を発見
(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)(8,0)(9,0)(9,1)
(9,2)(9,3)(9,4)(9,5)(9,6)(9,7)(9,8)(9,9)(8,9)(7,9)(7,8)
(7,7)(7,6)(7,5)(7,4)(7,3)(7,2)(6,2)(5,2)(4,2)(3,2)(2,2)
(2,3)(2,4)(3,4)(4,4)(5,4)(5,5)(5,6)(5,7)(5,8)(5,9)(4,9)
(3,9)(2,9)(1,9)(1,8)(1,7)(1,6)(0,6)
Yes


解説

HashSetで訪問済の座標を保持して、
再訪を防止しながら深さ優先探索してます。