Submission #11599167

---

Source Code Expand

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

namespace EX20
{
    public class Solve
    {
        public static void Main(string[] args)
        {
            new Atc001TasksDfs_a();
        }
    }
    public class Arc031_2
    {
        char umi = 'x';
        char riku = 'o';
        char[][] arr = new char[12][];
        bool[,] check = new bool[12, 12];
        int[] vy = { 1, 0, -1, 0 };
        int[] vx = { 0, 1, 0, -1 };

        public Arc031_2()
        {
            arr[0] = Enumerable.Repeat(umi, 12).ToArray();
            arr[11] = Enumerable.Repeat(umi, 12).ToArray();
            for (int i = 1; i <= 10; i++)
                arr[i] = $"{umi}{Ex.Read}{umi}".ToCharArray();

            for (int i = 0; i < 12; i++)
                for (int j = 0; j < 12; j++)
                    check[i, j] = true;

            if (Isok())
            {
                Write(true);
                return;
            }

            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                    if (arr[i][j] == umi)
                    {
                        arr[i][j] = riku;
                        if (Isok())
                        {
                            Write(true);
                            return;
                        }
                        arr[i][j] = umi;
                    }

            Write(false);
        }

        public void Clear()
        {
            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                    check[i, j] = (arr[i][j] == umi);
        }

        public bool Empty()
        {
            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                    if (!check[i, j])
                        return false;
            return true;
        }

        public void Isok(int i, int j)
        {
            for (int k = 0; k < 4; k++)
            {
                var x = i + vy[k];
                var y = j + vx[k];
                if (arr[x][y] == riku && !check[x, y])
                {
                    check[x, y] = true;
                    Isok(x, y);
                }
            }
        }

        public bool Isok()
        {
            Clear();

            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                {
                    if (arr[i][j] == riku)
                    {
                        Isok(i, j);
                        return Empty();
                    }
                }
            return true;
        }

        public void Write(bool b)
        {
            if (b) Console.WriteLine("YES");
            else Console.WriteLine("NO");
        }
    }
    public class Atc001TasksDfs_a
    {
        /// <summary>
        /// 街の南北の長さとして整数H
        /// </summary>
        int h;
        /// <summary>
        /// 東西の長さとして整数W
        /// </summary>
        int w;
        /// <summary>
        /// 格子状の街の各区画における状態
        /// s : その区画が家であることを表す。
        /// g : その区画が魚屋であることを表す。
        /// . : その区画が道であることを表す。
        /// # : その区画が塀であることを表す。
        /// </summary>
        char[][] arr;
        bool[][] check;
        int[] vy = { 1, 0, -1, 0 };
        int[] vx = { 0, 1, 0, -1 };

        public Atc001TasksDfs_a()
        {
            var i = Input();
            Write(dfs(i.Item1, i.Item2));
        }

        bool dfs(int i, int j)
        {
            if (arr[i][j] == '#') return false;
            if (check[i][j]) return false;
            check[i][j] = true;

            if (arr[i][j] == 'g')
            {
                return true;
            }


            for (int k = 0; k < 4; k++)
            {
                var x = i + vy[k];
                var y = j + vx[k];
                if (x >= 0 && y >= 0 && x < h && y < w)
                {
                    if (dfs(x, y)) return true;
                }
            }
            return false;
        }

        Tuple<int, int> Input()
        {
            var l1 = Ex.ReadIntArray();
            h = l1[0];
            w = l1[1];
            arr = new char[h][];
            check = new bool[h][];
            for (int i = 0; i < h; i++)
            {
                arr[i] = Ex.Read.ToCharArray();
                check[i] = new bool[w];
            }
            for (int i = 0; i < h; i++)
            {
                var idx = arr[i].ToList().IndexOf('s');
                if (idx >= 0)
                {
                    return Tuple.Create(i, idx);
                }
            }
            return Tuple.Create(0, 0);
        }

        public void Write(bool b)
        {
            if (b) Console.WriteLine("YES");
            else Console.WriteLine("NO");
        }
    }
    public class ABC_
    {
        public ABC_()
        {

        }
    }
    public static class Ex
    {
        public static void Cw(object s)
        {
            Console.WriteLine(s);
        }
        public static void Cw(bool b)
        {
            if (b) Cw("Yes");
            else Cw("No");
        }

        public static string Read { get { return Console.ReadLine().Trim(); } }
        public static int ReadInt { get { return int.Parse(Read); } }
        public static long ReadLong { get { return long.Parse(Read); } }
        public static double ReadDouble { get { return double.Parse(Read); } }
        public static string[] ReadArray() { return Read.Split(' '); }
        public static int[] ReadIntArray() { return Read.Split(' ').Select(s => int.Parse(s)).ToArray(); }
        public static long[] ReadLongArray() { return Read.Split(' ').Select(s => long.Parse(s)).ToArray(); }
        public static string[] ReadArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public static int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public static long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Submission Info

Judge Result