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

提出ソース

結果

問題	No.157 2つの空洞
ユーザー	14番
提出日時	2016-04-26 02:59:10
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	30 ms / 2,000 ms
コード長	5,963 bytes
コンパイル時間	976 ms
コンパイル使用メモリ	112,464 KB
実行使用メモリ	26,444 KB
最終ジャッジ日時	2024-10-04 15:52:48
合計ジャッジ時間	1,981 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	30 ms 24,396 KB
testcase_01	AC	26 ms 24,396 KB
testcase_02	AC	26 ms 26,352 KB
testcase_03	AC	25 ms 24,436 KB
testcase_04	AC	26 ms 24,368 KB
testcase_05	AC	25 ms 24,368 KB
testcase_06	AC	25 ms 26,444 KB
testcase_07	AC	25 ms 26,180 KB
testcase_08	AC	24 ms 26,180 KB
testcase_09	AC	24 ms 26,188 KB
testcase_10	AC	26 ms 24,240 KB
testcase_11	AC	25 ms 24,184 KB
testcase_12	AC	25 ms 24,184 KB
testcase_13	AC	26 ms 26,440 KB
testcase_14	AC	24 ms 22,448 KB
testcase_15	AC	25 ms 26,296 KB
testcase_16	AC	26 ms 26,044 KB
testcase_17	AC	27 ms 22,072 KB
testcase_18	AC	27 ms 24,052 KB
testcase_19	AC	26 ms 24,368 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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

ソースコード

raw source code

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
 
class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inpt = Reader.GetInt();
        int wLen = inpt[0];
        int hLen = inpt[1];
        
        this.Map = new char[hLen, wLen];
        
        for(int i=0; i<hLen; i++) {
            string tmp = Reader.ReadLine();
            for(int j=0; j<tmp.Length; j++) {
                this.Map[i, j] = tmp[j];
            }
        }
        this.Nuriwake();
        this.Step = new int[hLen, wLen];
        this.GetAns();
        
        Console.WriteLine(this.Ans);
        
    }
    
    private void GetAns() {
        Queue<int[]> task = new Queue<int[]>();
        for(int i=0; i<this.Map.GetLength(0); i++) {
            for(int j=0; j<this.Map.GetLength(1); j++) {
                if(this.Map[i,j] == 'A') {
                    List<int[]> nextPosList = new List<int[]>();
                    if(i > 0) {
                        nextPosList.Add(new int[]{i-1, j});
                    }
                    if(i < this.Map.GetLength(0)-1) {
                        nextPosList.Add(new int[]{i+1, j});
                    }
                    if(j>0) {
                        nextPosList.Add(new int[]{i, j-1});
                    }
                    if(j < this.Map.GetLength(1)-1) {
                        nextPosList.Add(new int[]{i, j+1});
                    }
                    foreach (int[] pos in nextPosList)
                    {
                        int x = pos[1];
                        int y = pos[0];
                        
                        if(Map[y,x] == '#') {
                            Step[y, x] = 1;
                            task.Enqueue(pos);
                        }
                    }
                    
                }
            }
        }
        
        while (task.Count > 0)
        {
            int[] pos = task.Dequeue();
            int x = pos[1];
            int y = pos[0];
            
            int nextStep = this.Step[y, x] + 1;
            
            List<int[]> nextPosList = new List<int[]>();
            if(x > 0) {
                nextPosList.Add(new int[]{y, x-1});
            }
            if(x < this.Map.GetLength(1)-1) {
                nextPosList.Add(new int[]{y, x+1});
            }
            if(y > 0) {
                nextPosList.Add(new int[]{y-1, x});
            }
            if(y < this.Map.GetLength(0)-1) {
                nextPosList.Add(new int[]{y+1, x});
            }
            foreach (int[] nextPos in nextPosList)
            {
                int nextY = nextPos[0];
                int nextX = nextPos[1];
                
                
                if(this.Map[nextY, nextX] == '#' && (this.Step[nextY, nextX] == 0 || this.Step[nextY, nextX] > nextStep)) {
                    this.Step[nextY, nextX] = nextStep;
                    task.Enqueue(nextPos);
                } else if(this.Map[nextY, nextX] == '.' && (this.Step[nextY, nextX] == 0 || this.Step[nextY, nextX] > nextStep)) {
                    this.Step[nextY, nextX] = nextStep;
                    this.Ans = Math.Min(this.Ans, nextStep - 1);
                }
            }
            
        }
    }
    
    private int Ans = int.MaxValue;
    private int[,] Step;    
    private void Nuriwake() {
        Queue<int[]> task = new Queue<int[]>();
        for(int i=0; i<this.Map.GetLength(0); i++) {
            for(int j=0; j<this.Map.GetLength(1); j++) {
                if(this.Map[i,j] == '.') {
                    task .Enqueue(new int[]{i,j});
                    break;
                }
            }
            if(task.Count > 0) {
                break;
            }
        }
        while (task.Count > 0)
        {
            int[] pos = task.Dequeue();
            int y = pos[0];
            int x = pos[1];
            this.Map[y, x] = 'A';
            List<int[]> nextPosList = new List<int[]>();
            if(x > 0) {
                nextPosList.Add(new int[]{y, x-1});
            }
            if(x < this.Map.GetLength(1)-1) {
                nextPosList.Add(new int[]{y, x+1});
            }
            if(y > 0) {
                nextPosList.Add(new int[]{y-1, x});
            }
            if(y < this.Map.GetLength(0)-1) {
                nextPosList.Add(new int[]{y+1, x});
            }
            foreach (int[] nextPos in nextPosList)
            {
                int nextY = nextPos[0];
                int nextX = nextPos[1];
                
                if(this.Map[nextY, nextX] == '.') {
                    this.Map[nextY, nextX] = 'A';
                    task.Enqueue(nextPos);
                }
            }
        }
        
        
        
    }
    
    private char[,] Map;
    


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




 
";
        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();
            }
        }
        public static int[] GetInt(char delimiter = ' ', bool trim = false)
        {
            string inptStr = ReadLine();
            if (trim)
            {
                inptStr = inptStr.Trim();
            }
            string[] inpt = inptStr.Split(delimiter);
            int[] ret = new int[inpt.Length];
            for (int i = 0; i < inpt.Length; i++)
            {
                ret[i] = int.Parse(inpt[i]);
            }
            return ret;
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード