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

😎 Решение:
import java.util.*;

public class Solution {
public int catMouseGame(int[][] graph) {
int n = graph.length;
final int DRAW = 0, MOUSE = 1, CAT = 2;
int[][][] dp = new int[n][n][2];
Queue queue = new LinkedList();

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.offer(new int[]{0, i, 0, MOUSE});
queue.offer(new int[]{0, i, 1, MOUSE});
queue.offer(new int[]{i, i, 0, CAT});
queue.offer(new int[]{i, i, 1, CAT});
}

while (!queue.isEmpty()) {
int[] state = queue.poll();
int mouse = state[0], cat = state[1], turn = state[2], winner = state[3];
for (int[] parent : 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.offer(new int[]{m, c, t, winner});
} else {
int degrees = 0;
for (int[] p : parents(graph, m, c, t)) degrees++;
if (degrees == 0) {
dp[m][c][t] = winner;
queue.offer(new int[]{m, c, t, winner});
}
}
}
}
}

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

private List parents(int[][] graph, int mouse, int cat, int turn) {
List res = new ArrayList();
if (turn == 1) {
for (int m : graph[mouse]) {
res.add(new int[]{m, cat, 0});
}
} else {
for (int c : graph[cat]) {
if (c > 0) res.add(new int[]{mouse, c, 1});
}
}
return res;
}
}

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