SRM420 DIV2 Level.2
パッと見てBFSだとわかるし、これぐらいの問題はすぐに解けないとだめだよな・・・。
結構時間かかってしまった。
using System; using System.Collections.Generic; using System.Text; public class Point { public int X; public int Y; public int D; public Point(int x, int y, int d) { this.X = x; this.Y = y; this.D = d; } } public class MazeWanderingEasy { public int decisions(String[] maze) { int lenX = maze.Length; int lenY = maze[0].Length; int[,] visited = new int[lenX, lenY]; int startX = 0, startY = 0; int[,] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; Queue<Point> q = new Queue<Point>(); int count = 0; for (int i = 0; i < lenX; i++) { for (int j = 0; j < lenY; j++) { if (maze[i][j] == 'M') { startX = i; startY = j; } } } Point p = new Point(startX, startY, 0); q.Enqueue(p); while (q.Count != 0) { Point h = q.Dequeue(); int x = h.X, y = h.Y; if (maze[x][y] == '*') { count = h.D; break; } visited[x, y] = 1; int m = 0; for (int i = 0; i < 4; i++) { int mx = x + move[i, 0]; int my = y + move[i, 1]; if (0 <= mx && mx < lenX && 0 <= my && my < lenY) { if ((visited[mx, my] == 0) && maze[mx][my] == '.' || maze[mx][my] == '*') { m++; } } } if (m >= 1) { for (int i = 0; i < 4; i++) { int mx = x + move[i, 0]; int my = y + move[i, 1]; if (0 <= mx && mx < lenX && 0 <= my && my < lenY) { if ((visited[mx, my] == 0) && maze[mx][my] == '.' || maze[mx][my] == '*') { Point tmp; if (m == 1) { tmp = new Point(mx, my, h.D); } else { tmp = new Point(mx, my, h.D + 1); } q.Enqueue(tmp); } } } } } return count; } }