結果

問題 No.157 2つの空洞
コンテスト
ユーザー bluemegane
提出日時 2018-10-05 20:06:05
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 2,267 bytes
コンパイル時間 942 ms
コンパイル使用メモリ 114,620 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-10-12 12:45:39
合計ジャッジ時間 2,283 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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

public class P
{
    public int x { get; set; }
    public int y { get; set; }
}

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var w = int.Parse(line[0]);
        var h = int.Parse(line[1]);
        var map = new int[h, w];
        var fx = 0; var fy = 0;
        var find = false;
        for (int i = 0; i < h; i++)
        {
            var s = Console.ReadLine().Trim();
            for (int j = 0; j < w; j++)
                if (s[j] == '.')
                {
                    if (!find) { fx = i; fy = j; find = true; }
                    map[i, j] = 1;
                }
        }
        var a1 = goDfs(map, fx, fy);
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (map[i, j] == 1) { fx = i; fy = j; goto next; }
        next:;
        var a2 = goDfs(map, fx, fy);
        var ans = getAns(a1, a2);
        Console.WriteLine(ans - 1);
    }
    public static int getAns(List<P> a, List<P> b)
    {
        var ans = int.MaxValue;
        foreach (var x in a)
            foreach (var y in b)
            {
                var w = Math.Abs(x.x - y.x) + Math.Abs(x.y - y.y);
                ans = Math.Min(ans, w);
            }
        return ans;
    }
    public static List<P> goDfs(int[,] map, int fx, int fy)
    {
        var ans = new List<P>();
        var h = map.GetLength(0);
        var w = map.GetLength(1);
        var dx = new int[] { 0, 1, 0, -1 };
        var dy = new int[] { 1, 0, -1, 0 };
        var q = new Queue<P>();
        q.Enqueue(new P { x = fx, y = fy });
        while (q.Count() > 0)
        {
            var a = q.Dequeue();
            if (map[a.x, a.y] != 2)
            {
                ans.Add(new P { x = a.x, y = a.y });
                map[a.x, a.y] = 2;
                for (int i = 0; i < 4; i++)
                {
                    var nx = a.x + dx[i];
                    var ny = a.y + dy[i];
                    if (nx >= 0 && nx < h && ny >= 0 && ny < w && map[nx, ny] == 1)
                        q.Enqueue(new P { x = nx, y = ny });
                }
            }
        }
        return ans;
    }
}
0