Задача: 913. Cat and Mouse4
Сложность: 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 (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

function catMouseGame($graph) {
    $n = count($graph);
    $DRAW = 0; $MOUSE = 1; $CAT = 2;
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
    $queue = [];

    for ($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[] = [0, $i, 0, $MOUSE];
        $queue[] = [0, $i, 1, $MOUSE];
        $queue[] = [$i, $i, 0, $CAT];
        $queue[] = [$i, $i, 1, $CAT];
    }

    function parents($graph, $mouse, $cat, $turn) {
        $res = [];
        if ($turn == 1) {
            foreach ($graph[$mouse] as $m) {
                $res[] = [$m, $cat, 0];
            }
        } else {
            foreach ($graph[$cat] as $c) {
                if ($c > 0) $res[] = [$mouse, $c, 1];
            }
        }
        return $res;
    }

    while (!empty($queue)) {
        list($mouse, $cat, $turn, $winner) = array_shift($queue);
        foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
            if ($dp[$m][$c][$t] == $DRAW) {
                if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
                    $dp[$m][$c][$t] = $winner;
                    $queue[] = [$m, $c, $t, $winner];
                } else {
                    $degrees = 0;
                    foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
                    if ($degrees == 0) {
                        $dp[$m][$c][$t] = $winner;
                        $queue[] = [$m, $c, $t, $winner];
                    }
                }
            }
        }
    }

    return $dp[1][2][0];
}

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