結果

問題 No.157 2つの空洞
コンテスト
ユーザー akichi
提出日時 2017-08-26 00:38:38
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 2,117 bytes
コンパイル時間 2,378 ms
コンパイル使用メモリ 107,904 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2024-10-15 16:21:07
合計ジャッジ時間 2,457 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.Drawing;
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];

        Point start = new Point();
        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;
                        start = new Point(x, y);
                    }
                }
                chars[x, y] = cs[x];
            }
        }

        dfs(start);

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

    static char[,] chars;
    static HashSet<Point> aa = new HashSet<Point>();
    static int w, h;

    static void dfs(Point p) {
        chars[p.X, p.Y] = 'A';
        aa.Add(p);

        Size[] dirs = { new Size(1, 0), new Size(-1, 0), new Size(0, 1), new Size(0, -1) };
        foreach (Size dir in dirs) {
            Point np = p + dir;
            if (np.X < 0 || w <= np.X || np.Y < 0 || h <= np.Y) {
                continue;
            }

            if (chars[np.X, np.Y] == '.') {
                dfs(np);
            }
        }
    }
}
0