結果

問題 No.157 2つの空洞
コンテスト
ユーザー syoken_desuka
提出日時 2015-02-27 00:03:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 5,102 bytes
コンパイル時間 993 ms
コンパイル使用メモリ 115,224 KB
実行使用メモリ 27,996 KB
最終ジャッジ日時 2024-06-23 21:50:17
合計ジャッジ時間 2,335 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using sc = Scanner;

class Program
{
    static void Main(string[] args)
    {
        Solve();

#if DEBUG
        System.Console.WriteLine("続行するには何かキーを押してください．．．");
        System.Console.ReadKey();
#endif

    }
    
    static int[,] Field;
    static int W;
    static int H;
    static int[] vx = { 1, 0, -1, 0 };
    static int[] vy = { 0, 1, 0, -1 };

    /// <summary>
    /// ここでとく
    /// </summary>
    static void Solve()
    {
        int w = sc.NextInt();
        int h = sc.NextInt();
        W = w;
        H = h;
        Field = new int[h, w];
        int min_displace = int.MaxValue;
        HashSet<Tuple<int,int>> group1 = new HashSet<Tuple<int,int>>();
        HashSet<Tuple<int,int>> group2 = new HashSet<Tuple<int,int>>();

        for (int i = 0; i < h; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < w; j++)
            {
                Field[i, j] = line[j] == '#' ? 1 : 0; 
            }
        }

        // group wakeru
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (Field[i,j] == 0)
                {
                    dfs(i, j, group1);
#if DEBUG
                    Console.WriteLine(1230000);
#endif 
                    i = h;
                    break;
                }
            }
        }
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (Field[i, j] == 0)
                {
                    dfs(i, j, group2);
                    break;
                }
            }
        }
        //man hatten kyori wo zenkeisan
        foreach (var item in group1)
        {
            foreach (var itemm in group2)
            {
                min_displace = Math.Min(min_displace, Math.Abs(item.Item1 - itemm.Item1) + Math.Abs(item.Item2 - itemm.Item2) - 1);
            }
        }

        Console.WriteLine(min_displace);
#if DEBUG
        Console.WriteLine("local check");
#endif 
    }

    static void dfs(int x, int y, HashSet<Tuple<int,int>> group)
    {
#if DEBUG
        Console.WriteLine(x+"  "+y);
#endif 
        Field[x , y] = 1;
        group.Add(new Tuple<int, int>(x , y ));
        for (int i = 0; i < 4; i++)
        {
            if ( x+vx[i] <0 || H <= x+vx[i] )
            {
                continue;
            }
            if (y + vy[i] < 0 || W <= y + vy[i])
            {
                continue;
            }

            if (Field[x+vx[i],y+vy[i]] == 0)
            {
                dfs(x + vx[i], y + vy[i], group);
                Field[x + vx[i], y + vy[i]] = 1;
            }                

        }
    }
}

/// <summary>
/// Java風のスキャナー，自作（某最速の人を参考）
/// </summary>
public static class Scanner
{
    public static string NextString()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return tmp;
    }

    public static string[] NextStrArray()
    {
        return Console.ReadLine().Split(' ');
    }

    public static long[] NextLongArray()
    {
        string[] s = NextStrArray();
        long[] a = new long[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = long.Parse(s[i]);
        }
        return a;
    }
    public static int[] NextIntArray()
    {

        string[] s = NextStrArray();
        int[] a = new int[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = int.Parse(s[i]);
        }
        return a;
    }
    public static int NextInt()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
        
            tmp += readData;
        }
        return int.Parse(tmp);
    }
    public static double NextDouble()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return double.Parse(tmp);
    }
    public static long NextLong()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return long.Parse(tmp);
    }
    public static double[] NextDoubleArray()
    {
        string[] s = NextStrArray();
        double[] a = new double[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = double.Parse(s[i]);
        }
        return a;
    }
}
0