TopCoder SRM 588: GameInDarknessDiv1

問題文

解法

###.###
###.###
###.###
...x...
#######

上のような「最大の深さが３以上の子ノードが３以上あるような地点 x」が存在して、 Bob が Alice より 2ターンか、それ以上早く先にその地点にたどり着くことができれば Bob の勝ち、それ以外は Alice の勝ちになる。

Bob が Alice より 1ターン先にたどり着ける場合

###.###
###.###
###.###
..AB...
#######

1ターン早くたどり着いても、その1ターン後に Alice が Bob に追いついてしまう。

子ノードの最大深さが2,3,3 だった場合

###Y###
###Y###
XXX.ZZZ
#######

説明のため上記のエリアを、Xスポット、Yスポット、Zスポットとしよう。

###.###
###y###
......A
#######

Bobの初期位置にかかわらず、深さ２のYスポットに Bob が逃げこんでも、 Alice が y 地点についた時点で Bob の負けが確定する。 y 地点に Bob がいなかったとしても、その１ターン後に Bob は Aliceのいる y 地点に移動せざるを得ない。
Alice からすると、 y に立ち寄るだけで、 Bob が隠れていないかどうかチェックすることができる。そのため、 y についてすぐ引き返せば、Bobがもう一方のXスポットに隠れたとしてもZスポット に移動することができない。あとは Alice が Xスポット を探索すれば Bob を捕まえられる。

ソース

public class GameInDarknessDiv1 {
    static public int[] dx = { 0, 1, 0, -1 };
    static public int[] dy = { 1, 0, -1, 0 };
    static public bool Between(long a, long x, long b) { return a <= x && x < b; }

    public struct Point {
        public int x, y, step;
    }

    int W, H;
    string[] field;

    public IEnumerable<Point> GetAdjacentEmptyCell(int x, int y) {
        var points = new List<Point>();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (Between(0, nx, W) && Between(0, ny, H) && field[ny][nx] != '#') {
                points.Add(new Point { x = nx, y = ny });
            }
        }
        return points;
    }

    public int[,] DistanceFrom(int x, int y) {
        int W = field[0].Length;
        int H = field.Length;
        var distance = new int[H, W];

        Queue<Point> qu = new Queue<Point>();
        qu.Enqueue(new Point { x = x, y = y, step=0 });
        var visited = new bool[H,W];
        while (qu.Any()) {
            Point p = qu.Dequeue();
            if (visited[p.y,p.x]) continue;
            visited[p.y,p.x] = true;
            distance[p.y, p.x] = p.step;
            foreach (var next in GetAdjacentEmptyCell(p.x, p.y)) {
                qu.Enqueue(new Point { x = next.x, y = next.y, step = p.step + 1 });
            }
        }

        return distance;
    }

    public bool Dfs(bool[,] visited, int x, int y, int depth = 1) {
        if (visited[y, x]) return false;
        visited[y, x] = true;
        if (depth == 3) return true;
        return GetAdjacentEmptyCell(x, y).Any(p => Dfs(visited, p.x, p.y, depth + 1));
    }

    public int CountDepth3Node(int x, int y) {
        var visited = new bool[H, W];
        visited[y,x] = true;
        return GetAdjacentEmptyCell(x, y).Count(p => Dfs(visited, p.x, p.y));
    }

    public string check(string[] field) {
        this.W = field[0].Length;
        this.H = field.Length;
        this.field = field;

        int[,] distanceFromAlice = null, distanceFromBob = null;
        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                if (field[y][x] == 'A')
                    distanceFromAlice = DistanceFrom(x, y);
                if (field[y][x] == 'B')
                    distanceFromBob = DistanceFrom(x, y);
            }
        }

        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                if (field[y][x] == '#') continue;
                if (distanceFromAlice[y, x] >= distanceFromBob[y, x] + 2) {
                    if (CountDepth3Node(x, y) >= 3) return "Bob wins";
                }
            }
        }

        return "Alice wins";
    }
}