using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Program { static void Main(string[] args) { int[] hw = Console.ReadLine().Split(" ").Select(int.Parse).ToArray(); int h = hw[0]; int w = hw[1]; char[,] map = new char[h, w]; int[] start = new int[2]; int[] goal = new int[2]; int[] enemy = new int[2]; for(int i = 0;i <= h - 1; i++) { char[] input = Console.ReadLine().ToCharArray(); for(int j = 0;j <= w - 1; j++) { map[i, j] = input[j]; if (input[j] == 'S') { start[0] = i; start[1] = j; } if (input[j] == 'G') { goal[0] = i; goal[1] = j; } if (input[j] == 'E') { enemy[0] = i; enemy[1] = j; } } } bool[,] reach1 = new bool[h, w]; Queue queue2 = new Queue(); void Reachability(int y,int x) { if(y > 0) { if (map[y - 1,x] != '#' && reach1[y - 1,x] == false) { reach1[y - 1, x] = true; queue2.Enqueue((y - 1).ToString() + " " + x.ToString()); } } if(y < h - 1) { if (map[y + 1,x] != '#' && reach1[y + 1,x] == false) { reach1[y + 1, x] = true; queue2.Enqueue((y + 1).ToString() + " " + x.ToString()); } } if(x > 0) { if (map[y,x - 1] != '#' && reach1[y,x - 1] == false) { reach1[y, x - 1] = true; queue2.Enqueue(y.ToString() + " " + (x - 1).ToString()); } } if(x < w - 1) { if (map[y,x + 1] != '#' && reach1[y,x + 1] == false) { reach1[y, x + 1] = true; queue2.Enqueue(y.ToString() + " " + (x + 1).ToString()); } } } queue2.Enqueue(start[0].ToString() + " " + start[1].ToString()); while(queue2.TryDequeue(out string pos)) { int[] p = pos.Split(" ").Select(int.Parse).ToArray(); Reachability(p[0], p[1]); } if (!reach1[goal[0], goal[1]]) { Console.WriteLine("No"); return; } bool[,] cycle = new bool[h, w]; int[,] edgecount = new int[h, w]; var nodequeue = new Queue(); for(int i = 0;i <= h - 1; i++) { for(int j = 0;j <= w - 1; j++) { if (map[i,j] != '#') { cycle[i, j] = true; } else { continue; } int count = 0; for(int k = 0;k <= 3; k++) { int x = j; int y = i; if(k == 0) { x += 1; } if(k == 1) { y += 1; } if(k == 2) { x -= 1; } if(k == 3) { y -= 1; } if(x >= 0 && x <= w - 1 && y >= 0 && y <= h - 1) { if (map[y,x] != '#') { count += 1; } } } edgecount[i,j] = count; if(count == 1) { nodequeue.Enqueue(i.ToString() + " " + j.ToString()); } } } while(nodequeue.Count > 0) { string memo = nodequeue.Dequeue(); int[] pos = memo.Split(" ").Select(int.Parse).ToArray(); cycle[pos[0], pos[1]] = false; for(int k = 0;k <= 3; k++) { int y = pos[0]; int x = pos[1]; if(k == 0) { x += 1; } if(k == 1) { y += 1; } if(k == 2) { x -= 1; } if(k == 3) { y -= 1; } if(x >= 0 && x <= w - 1 && y >= 0 && y <= h - 1) { if (map[y,x] != '#') { edgecount[y, x] -= 1; if (edgecount[y,x] == 1) { nodequeue.Enqueue(y.ToString() + " " + x.ToString()); } } } } } int[,] disP = new int[h, w]; int[,] disE = new int[h, w]; for(int i = 0;i <= h - 1; i++) { for(int j = 0;j <= w - 1; j++) { disP[i, j] = -1; disE[i, j] = -1; } } Queue queue = new Queue(); void BFS(int y,int x, bool P) { int d = 0; if (P) { d = disP[y, x]; } else { d = disE[y, x]; } for(int i = 0;i <= 3; i++) { int nextX = x; int nextY = y; if(i == 0) { nextX += 1; } if(i == 1) { nextY += 1; } if(i == 2) { nextX -= 1; } if(i == 3) { nextY -= 1; } if(nextX < 0 || nextX > w - 1 || nextY < 0 || nextY > h - 1) { continue; } if (map[nextY,nextX] == '#') { continue; } if (P) { if (disP[nextY,nextX] == -1) { queue.Enqueue(nextY.ToString() + " " + nextX.ToString()); disP[nextY, nextX] = d + 1; } } else { if (disE[nextY, nextX] == -1) { queue.Enqueue(nextY.ToString() + " " + nextX.ToString()); disE[nextY, nextX] = d + 1; } } } } queue.Enqueue(start[0].ToString() + " " + start[1].ToString()); disP[start[0], start[1]] = 0; while(queue.TryDequeue(out string str)) { int[] pos = str.Split(" ").Select(int.Parse).ToArray(); BFS(pos[0], pos[1], true); } queue.Clear(); queue.Enqueue(enemy[0].ToString() + " " + enemy[1].ToString()); disE[enemy[0], enemy[1]] = 0; while (queue.TryDequeue(out string str)) { int[] pos = str.Split(" ").Select(int.Parse).ToArray(); BFS(pos[0], pos[1], false); } bool answer = false; for(int i = 0;i <= h - 1; i++) { for(int j = 0;j <= w - 1; j++) { if(i == goal[0] && j == goal[1]) { if (disP[i,j] <= disE[i, j]) { bool checkgoal = false; for(int l = 0;l <= 3; l++) { int posY = i; int posX = j; if(l == 0) { posY -= 1; } if(l == 1) { posX -= 1; } if(l == 2) { posY += 1; } if(l == 3) { posX += 1; } if (posX >= 0 && posX <= w - 1 && posY >= 0 && posY <= h - 1) { if (disP[posY,posX] < disE[posY, posX] && map[posY,posX] != '#') { checkgoal = true; } } } if (checkgoal) { answer = true; } continue; } } if (cycle[i, j]) { if (disP[i,j] < disE[i, j]) { answer = true; continue; } } } } if (answer) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } }

提出日時
ユーザー	Tomo271828
言語	C# (Mono-mcs 6.12.0)
結果	CE
実行時間	ms
メモリ	kb

Game - Can you solve this maze?

コンパイルエラー