TopCoder SRM 588: GameInDarknessDiv2

問題文

アリスが移動できなくなるまで幅優先探索すればよい。
DP してもいいけれど、やっていることは結局同じになる。

public class GameInDarknessDiv2 {
    int[] dx = { 0, 1, 0, -1 };
    int[] dy = { 1, 0, -1, 0 };
    string ds = "DRUL";

    struct Point {
        public int row, col;
        public Point(int r, int c) {
            this.row = r;
            this.col = c;
        }
    }

    public string check(string[] field, string[] _moves) {
        string moves = String.Concat(_moves);
        int W = field[0].Length;
        int H = field.Length;

        Point Alice = new Point();
        Queue<Point> qu = new Queue<Point>();
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++) {
                if (field[i][j] == 'A')
                    Alice = new Point(i, j);
                if (field[i][j] == 'B')
                    qu.Enqueue(new Point(i, j));
            }

        foreach (var move in moves) {
            int dir = ds.IndexOf(move);
            Alice.row += dy[dir];
            Alice.col += dx[dir];

            Queue<Point> next = new Queue<Point>();
            bool[,] visited = new bool[H, W];

            while (qu.Count > 0) {
                Point Bob = qu.Dequeue();

                if (visited[Bob.row, Bob.col]) continue;
                visited[Bob.row, Bob.col] = true;

                if (Alice.row == Bob.row && Alice.col == Bob.col) continue;

                for (int i = 0; i < 4; i++) {
                    int nr = Bob.row + dy[i];
                    int nc = Bob.col + dx[i];
                    if (0 <= nr && nr < H && 0 <= nc && nc < W && field[nr][nc] != '#') {
                        if (Alice.row == nr && Alice.col == nc) continue;
                        next.Enqueue(new Point(nr, nc));
                    }
                }
            }

            qu = next;
        }

        return qu.Count() > 0 ? "Bob wins" : "Alice wins";
    }
}