913. Cat and Mouse
leetcode hard
Task
В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: 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
C# solution
matched/originalusing 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 };
}
}
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CatMouseGame(int[][] graph) {
int n = graph.size();
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.size() > 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 };
}
}
}
}Java solution
matched/originalimport 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<int[]> 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<int[]> parents(int[][] graph, int mouse, int cat, int turn) {
List<int[]> 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;
}
}Python solution
matched/originalfrom collections import deque
def catMouseGame(graph):
n = len(graph)
DRAW, MOUSE, CAT = 0, 1, 2
dp = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
queue = deque()
for i in range(1, n):
dp[0][i][0] = MOUSE
dp[0][i][1] = MOUSE
dp[i][i][0] = CAT
dp[i][i][1] = CAT
queue.append((0, i, 0, MOUSE))
queue.append((0, i, 1, MOUSE))
queue.append((i, i, 0, CAT))
queue.append((i, i, 1, CAT))
def parents(mouse, cat, turn):
if turn == 1:
for m in graph[mouse]:
yield (m, cat, 0)
else:
for c in graph[cat]:
if c > 0:
yield (mouse, c, 1)
while queue:
mouse, cat, turn, winner = queue.popleft()
for m, c, t in parents(mouse, cat, turn):
if dp[m][c][t] == DRAW:
if t == 0 and winner == MOUSE or t == 1 and winner == CAT:
dp[m][c][t] = winner
queue.append((m, c, t, winner))
else:
degrees = sum(1 for p in parents(m, c, t))
if degrees == 0:
dp[m][c][t] = winner
queue.append((m, c, t, winner))
return dp[1][2][0]Explanation
Algorithm
Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока.
Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).
Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.
😎