#199992 (C#(csc)) No.157 2つの空洞

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	33 ms; 19,968 KB
testcase_01	AC	34 ms; 20,224 KB
testcase_02	AC	33 ms; 20,224 KB
testcase_03	AC	33 ms; 20,224 KB
testcase_04	AC	32 ms; 20,224 KB
testcase_05	AC	34 ms; 20,096 KB
testcase_06	AC	33 ms; 20,224 KB
testcase_07	AC	34 ms; 20,352 KB
testcase_08	AC	33 ms; 20,224 KB
testcase_09	AC	33 ms; 20,608 KB
testcase_10	AC	33 ms; 20,224 KB
testcase_11	AC	32 ms; 20,096 KB
testcase_12	AC	32 ms; 20,352 KB
testcase_13	AC	33 ms; 20,224 KB
testcase_14	AC	33 ms; 20,224 KB
testcase_15	AC	33 ms; 20,224 KB
testcase_16	AC	33 ms; 20,096 KB
testcase_17	AC	33 ms; 20,224 KB
testcase_18	AC	32 ms; 20,096 KB
testcase_19	AC	32 ms; 20,224 KB

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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);
            }
        }
    }
}