Submission #420556


Source Code Expand

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

namespace ATC001
{
    public class A
    {
        private void Run()
        {
            var input = Console.ReadLine().Trim().Split();
            int H = int.Parse(input[0]);
            int W = int.Parse(input[1]);

            var field = Enumerable.Repeat(0, H).Select(_ => Console.ReadLine().Trim()).ToArray();
            int sx = -1, sy = -1, gx = -1, gy = -1;
            var uf = new UnionFind(H * W);
            for (int y = 0; y < H; y++)
            {
                for (int x = 0; x < W; x++)
                {
                    if (field[y][x] != '#')
                    {
                        if (0 < x && field[y][x - 1] != '#') { uf.Union(y * W + (x - 1), y * W + x); }
                        if (0 < y && field[y - 1][x] != '#') { uf.Union((y - 1) * W + x, y * W + x); }
                    }
                    if (field[y][x] == 's') { sx = x; sy = y; }
                    if (field[y][x] == 'g') { gx = x; gy = y; }
                }
            }
            Console.WriteLine(uf.IsSameSet(sy * W + sx, gy * W + gx) ? "Yes" : "No");
        }

        private static void Main()
        {
            var old = Console.Out;
            using (var writer = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false })
            {
                Console.SetOut(writer);
                new A().Run();
                Console.Out.Flush();
                Console.SetOut(old);
            }
        }

        public class UnionFind
        {
            public UnionFind(int elemCount) { this.m_a = Enumerable.Repeat(-1, elemCount).ToArray(); }
            public int Root(int x)
            {
                return this.m_a[x] < 0
                    ? x
                    : this.m_a[x] = this.Root(this.m_a[x]);
            }
            public bool Union(int x, int y)
            {
                x = Root(x);
                y = Root(y);
                if (x == y) { return false; }

                if (this.m_a[x] > this.m_a[y])
                {
                    var temp = this.m_a[x];
                    this.m_a[x] = this.m_a[y];
                    this.m_a[y] = temp;
                }
                this.m_a[x] += this.m_a[y];
                this.m_a[y] = x;
                return true;
            }
            public bool IsSameSet(int x, int y) { return this.Root(x) == this.Root(y); }
            public int Size(int x) { return -this.m_a[this.Root(x)]; }

            private readonly int[] m_a;
        }
    }
}

Submission Info

Submission Time
Task A - 深さ優先探索
User Tan90909090
Language C# (Mono 3.2.1.0)
Score 100
Code Size 2670 Byte
Status AC
Exec Time 186 ms
Memory 12868 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 186 ms 9632 KB
00_min_02.txt AC 124 ms 9616 KB
00_min_03.txt AC 125 ms 9632 KB
00_min_04.txt AC 126 ms 9620 KB
00_min_05.txt AC 127 ms 9664 KB
00_min_06.txt AC 121 ms 9616 KB
00_min_07.txt AC 120 ms 9636 KB
00_min_08.txt AC 125 ms 9620 KB
00_sample_01.txt AC 126 ms 9588 KB
00_sample_02.txt AC 123 ms 9632 KB
00_sample_03.txt AC 129 ms 9636 KB
00_sample_04.txt AC 122 ms 9636 KB
00_sample_05.txt AC 123 ms 9628 KB
01_rnd_00.txt AC 144 ms 12864 KB
01_rnd_01.txt AC 160 ms 12848 KB
01_rnd_02.txt AC 156 ms 12864 KB
01_rnd_03.txt AC 162 ms 12860 KB
01_rnd_04.txt AC 160 ms 12864 KB
01_rnd_05.txt AC 154 ms 12864 KB
01_rnd_06.txt AC 156 ms 12848 KB
01_rnd_07.txt AC 160 ms 12860 KB
01_rnd_08.txt AC 145 ms 12848 KB
01_rnd_09.txt AC 148 ms 12864 KB
01_rnd_10.txt AC 154 ms 12848 KB
01_rnd_11.txt AC 145 ms 12864 KB
01_rnd_12.txt AC 157 ms 12840 KB
01_rnd_13.txt AC 157 ms 12864 KB
01_rnd_14.txt AC 155 ms 12848 KB
01_rnd_15.txt AC 156 ms 12864 KB
01_rnd_16.txt AC 143 ms 12860 KB
01_rnd_17.txt AC 156 ms 12860 KB
01_rnd_18.txt AC 148 ms 12860 KB
01_rnd_19.txt AC 160 ms 12864 KB
02_rndhard_00.txt AC 159 ms 12860 KB
02_rndhard_01.txt AC 153 ms 12860 KB
02_rndhard_02.txt AC 156 ms 12864 KB
02_rndhard_03.txt AC 153 ms 12840 KB
02_rndhard_04.txt AC 153 ms 12864 KB
02_rndhard_05.txt AC 156 ms 12856 KB
02_rndhard_06.txt AC 154 ms 12864 KB
02_rndhard_07.txt AC 154 ms 12860 KB
02_rndhard_08.txt AC 158 ms 12836 KB
02_rndhard_09.txt AC 153 ms 12836 KB
02_rndhard_10.txt AC 155 ms 12860 KB
02_rndhard_11.txt AC 153 ms 12864 KB
02_rndhard_12.txt AC 154 ms 12860 KB
02_rndhard_13.txt AC 153 ms 12840 KB
02_rndhard_14.txt AC 160 ms 12864 KB
02_rndhard_15.txt AC 153 ms 12868 KB
02_rndhard_16.txt AC 154 ms 12848 KB
02_rndhard_17.txt AC 155 ms 12852 KB
02_rndhard_18.txt AC 156 ms 12864 KB
02_rndhard_19.txt AC 155 ms 12848 KB
02_rndhard_20.txt AC 155 ms 12844 KB
02_rndhard_21.txt AC 154 ms 12860 KB
02_rndhard_22.txt AC 156 ms 12864 KB
02_rndhard_23.txt AC 158 ms 12860 KB
02_rndhard_24.txt AC 158 ms 12848 KB
02_rndhard_25.txt AC 155 ms 12864 KB
02_rndhard_26.txt AC 154 ms 12864 KB
02_rndhard_27.txt AC 157 ms 12860 KB
02_rndhard_28.txt AC 152 ms 12864 KB
02_rndhard_29.txt AC 154 ms 12860 KB
02_rndhard_30.txt AC 156 ms 12860 KB
02_rndhard_31.txt AC 155 ms 12860 KB
02_rndhard_32.txt AC 156 ms 12832 KB
02_rndhard_33.txt AC 158 ms 12856 KB
02_rndhard_34.txt AC 155 ms 12864 KB
02_rndhard_35.txt AC 154 ms 12848 KB
02_rndhard_36.txt AC 157 ms 12864 KB
02_rndhard_37.txt AC 156 ms 12864 KB
02_rndhard_38.txt AC 157 ms 12864 KB
02_rndhard_39.txt AC 153 ms 12848 KB
03_rndhardsmall_00.txt AC 124 ms 9624 KB
03_rndhardsmall_01.txt AC 123 ms 9616 KB
03_rndhardsmall_02.txt AC 126 ms 9636 KB
03_rndhardsmall_03.txt AC 123 ms 9620 KB
03_rndhardsmall_04.txt AC 124 ms 9604 KB
03_rndhardsmall_05.txt AC 128 ms 9628 KB
03_rndhardsmall_06.txt AC 125 ms 9624 KB
03_rndhardsmall_07.txt AC 129 ms 9636 KB
03_rndhardsmall_08.txt AC 125 ms 9616 KB
03_rndhardsmall_09.txt AC 128 ms 9564 KB