結果
問題 |
No.367 ナイトの転身
|
ユーザー |
![]() |
提出日時 | 2016-05-13 18:51:24 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 3,368 bytes |
コンパイル時間 | 828 ms |
コンパイル使用メモリ | 114,844 KB |
実行使用メモリ | 24,064 KB |
最終ジャッジ日時 | 2024-10-05 16:34:54 |
合計ジャッジ時間 | 2,386 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
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; using System.Collections.Generic; using System.Linq; using System.IO; class Iroha { public Iroha() { } public static int Main() { new Iroha().calc(); return 0; } Scanner cin; int H, W; string[] board; void calc() { cin = new Scanner(); H = cin.nextInt(); W = cin.nextInt(); board = new string[H]; for (int i = 0; i < H; i++) { board[i] = cin.next(); } int fx = 0, fy = 0; int gx = 0, gy = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (board[i][j] == 'S') { fx = j; fy = i; } if (board[i][j] == 'G') { gx = j; gy = i; } } } int[] vy = { 1, 1, -1, -1 }; int[] vx = { 1, -1, 1, -1 }; int[] vy2 = { 2, 2, 1, 1, -1, -1, -2, -2 }; int[] vx2 = { 1, -1, 2, -2, 2, -2, 1, -1 }; int MAX = 99999999; int[,,] dist = new int[H, W, 2]; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { for (int k = 0; k < 2; k++) { dist[i, j, k] = MAX; } } } Queue<Tuple<int, int, int>> q = new Queue<Tuple<int, int, int>>(); dist[fy, fx, 0] = 0; q.Enqueue(Tuple.Create(fy, fx, 0)); while (q.Count > 0) { var now = q.Dequeue(); int y = now.Item1; int x = now.Item2; int z = now.Item3; int[] v1, v2; if (z == 0) { v1 = vy2; v2 = vx2; } else { v1 = vy; v2 = vx; } for (int k = 0; k < v1.Length; k++) { int ny = y + v1[k]; int nx = x + v2[k]; int nz = z; if (!inside(ny, nx)) continue; if (board[ny][nx] == 'R') nz ^= 1; if (dist[ny, nx, nz] != MAX) continue; dist[ny, nx, nz] = dist[y, x, z] + 1; if (ny == gy && nx == gx) { Console.WriteLine(dist[ny, nx, nz]); return; } q.Enqueue(Tuple.Create(ny, nx, nz)); } } Console.WriteLine(-1); } bool inside(int y, int x) { return y >= 0 && x >= 0 && y < H && x < W; } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return next(); } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }