Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

👨‍💻 Алгоритм:

1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока.

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int CatMouseGame(int[][] graph) {
        int n = graph.Length;
        const int DRAW = 0, MOUSE = 1, CAT = 2;
        int[,,] dp = new int[n, n, 2];
        Queue<int[]> queue = new Queue<int[]>();

        for (int i = 1; i < n; i++) {
            dp[0, i, 0] = MOUSE;
            dp[0, i, 1] = MOUSE;
            dp[i, i, 0] = CAT;
            dp[i, i, 1] = CAT;
            queue.Enqueue(new int[] { 0, i, 0, MOUSE });
            queue.Enqueue(new int[] { 0, i, 1, MOUSE });
            queue.Enqueue(new int[] { i, i, 0, CAT });
            queue.Enqueue(new int[] { i, i, 1, CAT });
        }

        while (queue.Count > 0) {
            var state = queue.Dequeue();
            int mouse = state[0], cat = state[1], turn = state[2], winner = state[3];
            foreach (var parent in Parents(graph, mouse, cat, turn)) {
                int m = parent[0], c = parent[1], t = parent[2];
                if (dp[m, c, t] == DRAW) {
                    if ((t == 0 && winner == MOUSE) || (t == 1 && winner == CAT)) {
                        dp[m, c, t] = winner;
                        queue.Enqueue(new int[] { m, c, t, winner });
                    } else {
                        int degrees = 0;
                        foreach (var _ in Parents(graph, m, c, t)) degrees++;
                        if (degrees == 0) {
                            dp[m, c, t] = winner;
                            queue.Enqueue(new int[] { m, c, t, winner });
                        }
                    }
                }
            }
        }

        return dp[1, 2, 0];
    }

    private IEnumerable<int[]> Parents(int[][] graph, int mouse, int cat, int turn) {
        if (turn == 1) {
            foreach (int m in graph[mouse]) {
                yield return new int[] { m, cat, 0 };
            }
        } else {
            foreach (int c in graph[cat]) {
                if (c > 0) yield return new int[] { mouse, c, 1 };
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний