結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー 14番
提出日時 2016-09-01 08:05:53
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 4,759 bytes
コンパイル時間 2,589 ms
コンパイル使用メモリ 109,696 KB
実行使用メモリ 935,848 KB
最終ジャッジ日時 2024-11-15 16:31:33
合計ジャッジ時間 26,132 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 14 TLE * 3 MLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Text;
using System.Linq;


class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        int h = inpt[0];
        int w = inpt[1];

        char[,] map = new char[h, w];

        Queue<int[]> taskQue = new Queue<int[]>();
        bool[,] initFlag = new bool[h, w];

        for (int i = 0; i < inpt[0]; i++)
        {
            string row = Reader.ReadLine();
            for (int j = 0; j < inpt[1]; j++)
            {
                map[i, j] = row[j];
                if (row[j] == '.')
                {
                    for (int k = Math.Max(0, i - 1); k <= Math.Min(h - 1, i + 1); k++)
                    {
                        for (int l = Math.Max(0, j - 1); l <= Math.Min(w - 1, j + 1); l++)
                        {
                            if(i==k && l==j) {
                                continue;
                            }
                            if (!initFlag[k, l])
                            {
                                initFlag[k, l] = true;
                                taskQue.Enqueue(new int[] { k, l });
                            }
                        }
                    }
                }
                else if (i == 0 || i == h - 1 || j == 0 || j == w - 1)
                {
                    if (!initFlag[i, j])
                    {
                        initFlag[i, j] = true;
                        taskQue.Enqueue(new int[] { i, j });
                    }
                }
            }
        }


        int[,] step = new int[h, w];
        int maxNewval = 0;
        while (taskQue.Count > 0)
        {
            int[] pos = taskQue.Dequeue();

            if(map[pos[0], pos[1]] == '.') {
                continue;
            }
            int oldVal = step[pos[0], pos[1]];

            int newVal = oldVal;
            if (pos[0] == 0 || pos[0] == h - 1 || pos[1] == 0 || pos[1] == w - 1)
            {
                newVal = 1;
            }
            else
            {
                for (int i = pos[0] - 1; i <= pos[0] + 1; i++)
                {
                    bool mustBreak = false;
                    for (int j = pos[1] - 1; j <= pos[1] + 1; j++)
                    {
                        if (i == pos[0] && j == pos[1])
                        {
                            continue;
                        }
                        if (map[i, j] == '.')
                        {
                            newVal = 1;
                            mustBreak = true;
                            break;
                        }
                        else if (step[i, j] > 0)
                        {
                            if (newVal == 0)
                            {
                                newVal = step[i, j] + 1;
                            }
                            else
                            {
                                newVal = Math.Min(newVal, step[i, j] + 1);
                            }
                        }
                    }
                    if (mustBreak)
                    {
                        break;
                    }
                }
            }
            if (oldVal != newVal)
            {
                step[pos[0], pos[1]] = newVal;
                maxNewval = Math.Max(maxNewval, newVal);
                for (int i = Math.Max(0, pos[0] - 1); i <= Math.Min(h - 1, pos[0] + 1); i++)
                {
                    for (int j = Math.Max(0, pos[1] - 1); j <= Math.Min(w - 1, pos[1] + 1); j++)
                    {
                        if (i == pos[0] && j == pos[1])
                        {
                            continue;
                        }
                        taskQue.Enqueue(new int[] { i, j });
                    }
                }
            }
        }
        Console.WriteLine(maxNewval);
    
    }




    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"


8 8
.#..#...
.######.
#####...
#####.#.
########
######.#
#####...
...####.




";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0