Submission #1513400


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;
using static CS_Contest.Utils;
using System.IO;
//using static CS_Contest.Library;

namespace CS_Contest {
	using Li = List<int>;
	using LLi = List<List<int>>;
	using Ls = List<string>;
	class Program {
		static void Main(string[] args) {
			var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
			SetOut(sw);
			new Calc().Solve();

			return;
        }

		private class Calc {
			private List<char[]> Box = new List<char[]>();
			Li RC, S, G;
			public void Solve() {
				RC = ReadInt(' ');
				S = ReadInt(' ');
				G = ReadInt(' ');
				REP(RC[0], _ => {
					Box.Add(ReadLine().Where(x => x != 32).ToArray());
				});
				BFS(S[1]-1, S[0]-1).WL();
				Out.Flush();
				return;
			}
			private int[] DirX = new int[] { 0, 1, 0, -1 };
			private int[] DirY = new int[] { 1, 0, -1, 0 };
			private int BFS(int x,int y) {
				Queue<Vector2> Q = new Queue<Vector2>();
				Q.Enqueue(new Vector2 { X = x, Y = y });
				int step = 0;
				while (Q.Count!=0) {
					var qsrc = Q;
					Queue<Vector2> tmp = new Queue<Vector2>();
					foreach (var src in qsrc) {
						for (int i = 0; i < 4; i++) {
							int xx = src.X + DirX[i], yy = src.Y + DirY[i];
							if (xx < 0 || yy < 0 || xx >= RC[1] || y >= RC[0]) continue;
							if (Box[yy][xx] == '_' || Box[yy][xx] == '#') continue;
							if (xx == G[1] - 1 && yy == G[0] - 1) return step+1;
							Box[yy][xx] = '_';
							tmp.Enqueue(new Vector2 { X = xx, Y = yy });
						}
					}
					step++;
					Q = tmp;
				}
				return 0;
			}
		}
	}


	public static class Utils {
		public static int ModValue = (int)(1e9+7);
		public static long INF = long.MaxValue;
		public static long Mod(long x) => x % ModValue;
		public static long ModPow(long x,long n) { long tmp = 1; while (n != 0) { if (n % 2 == 1) { tmp = Mod(tmp * x); }x = Mod(x * x);n /= 2; }return tmp; }
		public static long DivMod(long x, long y) => Mod(x * ModPow(y, (long)(1e9 + 5)));
        public static void WL(this object obj) => WriteLine(obj);
        public static void WL(this string obj) => WriteLine(obj);
        public static void WL<T>(this IEnumerable<T> list) => list.ToList().ForEach(x => x.WL());
		public static int ReadInt() => int.Parse(ReadLine());
		public static List<int> ReadInt(char s) => ReadLine().Split(s).Where(x=>x!="").Select(int.Parse).ToList();
		public static long ReadLong() => long.Parse(ReadLine());
		public static List<long> ReadLong(char s) => ReadLine().Split(s).Select(long.Parse).ToList();
		public static void ReadMulti(out int x, out int y) {
			var i = ReadInt(' ');
			x = i[0]; y = i[1];

		}
		public static void ReadMulti(out long x, out long y) {
			var i = ReadLong(' ');
			x = i[0];y = i[1];
		}
		public static void ReadMulti(out int x, out int y, out int z) {
			var i = ReadInt(' ');
			x = i[0];y = i[1];z = i[2];
		}
		public static void ReadMulti(out int x, out int y, out int z, out int v) {
			var i = ReadInt(' ');
			x = i[0]; y = i[1]; z = i[2];v = i[3];
		}

		public static long GCD(long m,long n) {
			long tmp;
			while(m%n!=0) {
				tmp = n;
				n = m % n;
				m = tmp;
			}
			return n;
		}
		public static long LCM(long m, long n) => m * (n / GCD(m, n));

		public static void REP(int n,Action<int> act) {
			for (int i = 0; i < n; i++) {
				act(i);
			}
		}
		public static void RREP(int n,Action<int> act) {
			for (int i = n-1; i >=0; i--) {
				act(i);
			}
		}
		public static void REP(long n, Action<int> act) => REP((int)n, act);
		public static void RREP(long n, Action<int> act) => RREP((int)n, act);

		public static void Yes() => "Yes".WL();
		public static void No() => "No".WL();
		public static void YES() => "YES".WL();
		public static void NO() => "NO".WL();


		public static int ManhattanDistance(int x1, int y1, int x2, int y2) => Abs(x2 - x1) + Abs(y2 - y1);


		public class Vector2 {
			public int X { get; set; }
			public int Y { get; set; }
			public Vector2() { X = 0; Y = 0; }
			public Vector2(int x, int y) { X = x; Y = y; }
			public int ManhattanDistance(Vector2 v2) {
				return Utils.ManhattanDistance(X, Y, v2.X, v2.Y);
			}
			public static int ManhattanDistance(Vector2 v1, Vector2 v2) => v2.ManhattanDistance(v2);
			public double Distance(Vector2 v2) => Sqrt(Pow(X - v2.X, 2) + Pow(Y - v2.Y, 2));
			public static Vector2 Zero { get { return new Vector2(); } }
			public void Clear() { X = 0; Y = 0; }
		}


	}
}

Submission Info

Submission Time
Task C - 幅優先探索
User xztaityozx
Language C# (Mono 4.6.2.0)
Score 100
Code Size 4672 Byte
Status AC
Exec Time 32 ms
Memory 13652 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 31 ms 11604 KB
subtask0_sample02.txt AC 30 ms 9684 KB
subtask0_sample03.txt AC 31 ms 11476 KB
subtask1_01.txt AC 30 ms 9428 KB
subtask1_02.txt AC 31 ms 13524 KB
subtask1_03.txt AC 32 ms 13524 KB
subtask1_04.txt AC 31 ms 11476 KB
subtask1_05.txt AC 31 ms 11476 KB
subtask1_06.txt AC 31 ms 11604 KB
subtask1_07.txt AC 30 ms 11476 KB
subtask1_08.txt AC 30 ms 11476 KB
subtask1_09.txt AC 31 ms 11476 KB
subtask1_10.txt AC 31 ms 13524 KB
subtask1_11.txt AC 30 ms 9428 KB
subtask1_12.txt AC 30 ms 9428 KB
subtask1_13.txt AC 30 ms 11476 KB
subtask1_14.txt AC 31 ms 13524 KB
subtask1_15.txt AC 31 ms 13652 KB
subtask1_16.txt AC 31 ms 11476 KB
subtask1_17.txt AC 31 ms 11476 KB
subtask1_18.txt AC 31 ms 11476 KB
subtask1_19.txt AC 31 ms 11476 KB
subtask1_20.txt AC 31 ms 11476 KB
subtask1_21.txt AC 31 ms 11604 KB
subtask1_22.txt AC 31 ms 11604 KB