#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

ファイルパターン	結果
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.

ソースコード

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