Submission #1315925


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;

namespace AIZU
{
	struct V
	{
		public V(int ny, int nx) { x = nx; y = ny; }
		public int x;
		public int y;
		public static V operator +(V a, V b) => new V(a.y+ b.y, a.x + b.x);
		public static bool operator ==(V a, V b) => a.x == b.x && a.y == b.y;
		public static bool operator !=(V a, V b) => a.x != b.x || a.y != b.y;
		public override string ToString() => $"{x},{y}";
		public override bool Equals(object X) { if (X == null || !(X is V)) return false; return (V)X == this; }
		public override int GetHashCode() => base.GetHashCode();
	}
	class Program
	{
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			int g;
			for (int i = 0; i < ss.Length; i++) {
				if (int.TryParse(ss[i], out g))
					Res[i] = g;
			}
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static long[] lins(char spliter)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new long[] { };
			string[] ss = s.Split(spliter);
			long[] Res = new long[ss.Length];
			long g;
			for (int i = 0; i < ss.Length; i++) {
				if (long.TryParse(ss[i], out g))
					Res[i] = g;
			}
			return Res;
		}
		static long[] lins() { return lins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		#endregion
		static bool[,] Pass;
		static bool BOP (V v){
			return Pass[v.y,v.x];
		}
		static void Main(string[] args)
		{
			int[] I = cins();
			int R = I[0], C = I[1];
			Pass = new bool[R, C]; ;
			I = cins();
			int sy = I[0] - 1, sx = I[1] - 1;
			I = cins();
			int gy = I[0] - 1, gx = I[1] - 1;
			string Road;
			for (int iop = 0; iop < R; iop++) {
				Road = Console.ReadLine();
				for (int jop = 0; jop < C; jop++) {
					Pass[iop, jop] = Road[jop] == '.';
				}
			}

			print(Explore(new V(sy,sx),new V(gy,gx)));
			Console.ReadLine();
		}
		static Queue<V> Frontier = new Queue<V>();
		static V[]Adja = new V[]{ new V(1,0),new V(0,1),new V(-1,0),new V(0,-1) };
		static int Explore(V v0, V goal)
		{
			HashSet<V> G = new HashSet<V>();
			G.Clear();
			Frontier.Enqueue(v0); G.Add(v0);
			V v;
			int level = 0;
			int beta = 0;
			while (Frontier.Count > 0) {
				if (beta == 0) { level++; beta = Frontier.Count(); }
				v = Frontier.Peek();
				foreach (V d in Adja) {
					if (!BOP(v+d) || G.Contains(v + d)) continue;
					Frontier.Enqueue(v + d); G.Add(v + d);
					if (v + d == goal) goto E;
				}
				Frontier.Dequeue();
				beta--;
			}
			E:
			return level;
		}
	}
}

Submission Info

Submission Time
Task C - 幅優先探索
User sa8
Language C# (Mono 4.6.2.0)
Score 100
Code Size 3003 Byte
Status AC
Exec Time 33 ms
Memory 15436 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 28 ms 11348 KB
subtask0_sample02.txt AC 29 ms 11348 KB
subtask0_sample03.txt AC 32 ms 13408 KB
subtask1_01.txt AC 29 ms 11420 KB
subtask1_02.txt AC 29 ms 11420 KB
subtask1_03.txt AC 29 ms 9372 KB
subtask1_04.txt AC 32 ms 13408 KB
subtask1_05.txt AC 30 ms 11420 KB
subtask1_06.txt AC 30 ms 11420 KB
subtask1_07.txt AC 28 ms 9300 KB
subtask1_08.txt AC 28 ms 11348 KB
subtask1_09.txt AC 29 ms 9372 KB
subtask1_10.txt AC 29 ms 9300 KB
subtask1_11.txt AC 33 ms 15436 KB
subtask1_12.txt AC 31 ms 13468 KB
subtask1_13.txt AC 30 ms 11420 KB
subtask1_14.txt AC 28 ms 11348 KB
subtask1_15.txt AC 29 ms 11420 KB
subtask1_16.txt AC 29 ms 9372 KB
subtask1_17.txt AC 30 ms 11548 KB
subtask1_18.txt AC 30 ms 11420 KB
subtask1_19.txt AC 28 ms 9372 KB
subtask1_20.txt AC 29 ms 11420 KB
subtask1_21.txt AC 30 ms 11420 KB
subtask1_22.txt AC 29 ms 11420 KB