結果

問題 No.157 2つの空洞
コンテスト
ユーザー bluemegane
提出日時 2018-10-05 19:54:52
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,125 bytes
コンパイル時間 1,049 ms
コンパイル使用メモリ 107,008 KB
実行使用メモリ 323,396 KB
最終ジャッジ日時 2024-10-12 12:45:20
合計ジャッジ時間 5,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 1 -- * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = new List<int>();
        foreach (var x in a)
            foreach (var y in b)
                ans.Add(Math.Abs(x.x - y.x) + Math.Abs(x.y - y.y));
        return ans.Min();
    }
    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