結果

問題 No.367 ナイトの転身
コンテスト
ユーザー 14番
提出日時 2016-05-18 20:17:39
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 574 ms / 2,000 ms
コード長 5,144 bytes
コンパイル時間 856 ms
コンパイル使用メモリ 116,004 KB
実行使用メモリ 45,372 KB
最終ジャッジ日時 2024-10-06 05:37:32
合計ジャッジ時間 4,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
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];
        this.Map = new char[H,W];
        this.Step = new MapStatus[H,W];
        int goalX = 0;
        int goalY = 0;
        
        TaskItem firstTask = new TaskItem();
        for(int i=0; i<H; i++) {
            string str = Reader.ReadLine();
            for(int j=0; j<str.Length; j++) {
                this.Map[i,j] = str[j];
                MapStatus newItem = new MapStatus();
                if(str[j] == 'S') {
                    newItem.Bishop = 0;
                    newItem.Knight = 0;
                    firstTask.X = j;
                    firstTask.Y = i;
                    firstTask.IsKnight = true;
                } else if(str[j] == 'G') {
                    goalX = j;
                    goalY = i;
                }
                this.Step[i,j] = newItem;
            }
        }
        
        Queue<TaskItem> task = new Queue<TaskItem>();
        task.Enqueue(firstTask);
        while (task.Count > 0)
        {
            TaskItem t = task.Dequeue();
            bool isKnight = t.IsKnight;
            int step = this.Step[t.Y, t.X].Knight;
            if(!isKnight) {
                step = this.Step[t.Y, t.X].Bishop;
            }
            if(Map[t.Y, t.X] == 'R') {
                isKnight = !isKnight;
            }
            if(this.Map[t.Y, t.X] == 'G') {
                continue;
            }
            List<Pos> next = this.GetNextMoveTo(new Pos(t.X, t.Y), isKnight);
            next.ForEach((a)=>{
                if(isKnight) {
                    if(Step[a.Y, a.X].Knight > step + 1) {
                        this.Step[a.Y, a.X].Knight = step + 1;
                        TaskItem newT = new TaskItem();
                        newT.Y = a.Y;
                        newT.X = a.X;
                        newT.IsKnight = true;
                        task.Enqueue(newT);
                    }
                } else
                {
                    if(Step[a.Y, a.X].Bishop > step + 1) {
                        this.Step[a.Y, a.X].Bishop = step + 1;
                        TaskItem newT = new TaskItem();
                        newT.Y = a.Y;
                        newT.X = a.X;
                        newT.IsKnight = false;
                        task.Enqueue(newT);
                    }
                }
            });
        }
        int ans = Math.Min(Step[goalY, goalX].Bishop, Step[goalY, goalX].Knight);
        if(ans == int.MaxValue) {
            ans = -1;
        }
        Console.WriteLine(ans);
        
    }
    
    private List<Pos> GetNextMoveTo(Pos nowPos, bool isKnight) {
        Pos[] tmp;
        if(isKnight) {
            tmp = new Pos[8];
            tmp[0] = new Pos(nowPos.X + 2, nowPos.Y + 1);
            tmp[1] = new Pos(nowPos.X + 2, nowPos.Y - 1);
            tmp[2] = new Pos(nowPos.X - 2, nowPos.Y + 1);
            tmp[3] = new Pos(nowPos.X - 2, nowPos.Y - 1);
            tmp[4] = new Pos(nowPos.X + 1, nowPos.Y + 2);
            tmp[5] = new Pos(nowPos.X - 1, nowPos.Y + 2);
            tmp[6] = new Pos(nowPos.X + 1, nowPos.Y - 2);
            tmp[7] = new Pos(nowPos.X - 1, nowPos.Y - 2);
        } else
        {
            tmp = new Pos[4];
            tmp[0] = new Pos(nowPos.X + 1, nowPos.Y + 1);
            tmp[1] = new Pos(nowPos.X + 1, nowPos.Y - 1);
            tmp[2] = new Pos(nowPos.X - 1, nowPos.Y + 1);
            tmp[3] = new Pos(nowPos.X - 1, nowPos.Y - 1);
        }
        List<Pos> ret = new List<Pos>();
        
        tmp.ToList().ForEach((a)=>{
           if(a.X >= 0 && a.X < Map.GetLength(1) && a.Y >= 0 && a.Y < Map.GetLength(0)) {
               ret.Add(a);
           } 
        });
        return ret;
    }
    
    private char[,] Map;
    
    private MapStatus[,] Step;
    
    public class Pos {
        public int X;
        public int Y;
        
        public Pos(int x, int y) {
            this.X = x;
            this.Y = y;
        }
    }

    public class TaskItem {
        public int X;
        public int Y;
        
        public bool IsKnight;
    }
    
    public class MapStatus {
        public int Bishop = int.MaxValue;
        public int Knight = int.MaxValue;
        
    }    

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


3 3
.R.
RGR
SR.

 
";
        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