結果

問題 No.157 2つの空洞
コンテスト
ユーザー akichi
提出日時 2017-08-26 01:08:39
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,192 bytes
コンパイル時間 1,209 ms
コンパイル使用メモリ 110,844 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2024-10-15 16:22:09
合計ジャッジ時間 2,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.Linq;
class Program {

    static void Main() {
        int[] wh = Console.ReadLine().Split().Select(int.Parse).ToArray();
        w = wh[0]; h = wh[1];
        chars = new char[w, h];
        int startX = 0, startY = 0;
        bool dotFound = false;
        for (int y = 0; y < h; y++) {
            string cs = Console.ReadLine();
            for (int x = 0; x < w; x++) {
                if (cs[x] == '.') {
                    if (!dotFound) {
                        dotFound = true;
                        startX = x; startY = y;
                    }
                }
                chars[x, y] = cs[x];
            }
        }

        dfs(startX, startY);

        int ans = 1000;
        foreach (var a in aPosi) {
            for (int dx = -1; dx <= 1; dx += 2) {
                for (int x = a.Item1; 0 <= x && x < w; x += dx) {
                    for (int dy = -1; dy <= 1; dy += 2) {
                        for (int y = a.Item2; 0 <= y && y < h; y += dy) {
                            if (x == a.Item1 && y == a.Item2) continue;
                            if (chars[x, y] == 'A') break;
                            if (chars[x, y] == '.') {
                                int score = Math.Abs(a.Item1 - x) + Math.Abs(a.Item2 - y) - 1;
                                ans = Math.Min(ans, score);
                                break;
                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine(ans);
    }

    static char[,] chars;
    static int w, h;
    static HashSet<Tuple<int, int>> aPosi = new HashSet<Tuple<int, int>>();
    static void dfs(int x, int y) {
        chars[x, y] = 'A';
        aPosi.Add(Tuple.Create(x, y));
        for (int i = 0; i < 4; i++) {
            int pm = 1 - (i % 2) * 2;
            int dx = (1 - i / 2) * pm;
            int dy = i / 2 * pm;

            int nx = x + dx, ny = y + dy;
            if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
                continue;
            }

            if (chars[nx, ny] == '.') {
                dfs(nx, ny);
            }
        }
    }
}
0