Jozwik_solution2.py

# Aleksander Jóźwik
# Złożoność: O((NM)^(3k)), gdzie k - liczba figur

from data import runtests
from collections import deque

def get_moves_for_kind(kind : str, i, j, N, M, allowed : set, occupied : set) -> list[tuple[int, int]]:
    '''
    Zwraca listę pól, do których dana figura może się przesunąć z pozycji (i, j).

    Zasady ruchu:
      - "k": król – 1 krok w dowolnym z 8 kierunków;
      - "n": skoczek – 8 ustalonych przesunięć;
      - "r": wieża – ruchy poziome i pionowe (przesuwamy się aż do przeszkody);
      - "b": goniec – ruchy diagonalne;
      - "q": hetman – suma ruchów wieży i goniec.
      
    Przyjmujemy, że przeszkodą są:
      - wyjście poza planszę,
      - pole nie należące do allowed (dziury),
      - pole już zajęte przez inną figurę.
    '''
    moves = []

    if kind == 'k':
        for di in (-1, 0, 1):
            for dj in (-1, 0, 1):
                if di == dj == 0: continue
                ni, nj = i + di, j + dj
                if 1 <= ni <= N and 1 <= nj <= M and (ni, nj) in allowed and (ni, nj) not in occupied:
                    moves.append((ni, nj))
    elif kind == 'n':
        jumps = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]        
        for di, dj in jumps:
            ni, nj = i + di, j + dj
            if 1 <= ni <= N and 1 <= nj <= M and (ni, nj) in allowed and (ni, nj) not in occupied:
                moves.append((ni, nj))
    elif kind == 'r':
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            while 1 <= ni <= N and 1 <= nj <= M and (ni, nj) in allowed and (ni, nj) not in occupied:
                moves.append((ni, nj))
                ni += di
                nj += dj
    elif kind == 'b':
        dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            while 1 <= ni <= N and 1 <= nj <= M and (ni, nj) in allowed and (ni, nj) not in occupied:
                moves.append((ni, nj))
                ni += di
                nj += dj
    else: # kind == 'q'
        moves_as_r = get_moves_for_kind('r', i, j, N, M, allowed, occupied)
        moves_as_b = get_moves_for_kind('b', i, j, N, M, allowed, occupied)
        moves = list(set(moves_as_r + moves_as_b))

    return moves


def build_graph_of_states(N, M, holes : list, pieces : list) -> list[set[int]]:
    '''
    Buduje graf stanów gry wg następującej zasady:
    1. Stan gry reprezentowany jest jako uporządkowana (posortowana) krotka pozycji figur,
        gdzie każda figura opisana jest przez (kind, i, j).
    2. Dla danego stanu rozpatrujemy każdy ruch każdej figury. Jeśli wynikowy stan już istnieje,
        dodajemy krawędź (graf traktujemy jako nieskierowany), w przeciwnym przypadku tworzymy nowy wierzchołek.
    
    Parametry:
      N, M           - wymiary planszy.
      holes          - lista dziur.
      pieces - lista początkowych pozycji figur, np. [("k", 1, 2), ("q", 3, 3), ...]
    
    Zwraca:
      graph: lista sąsiedztwa, gdzie graph[id] to zbiór identyfikatorów stanów sąsiadujących z danym stanem.
    '''
    holes_set = set(holes)
    allowed = {(i, j) for i in range(1, N + 1) for j in range(1, M + 1) if (i, j) not in holes_set}

    pieces.sort() # standaryzacja stanu gry do porównywania i hashowania
    s = tuple(pieces)

    state_to_id = {s : 0}
    state_list = [s]
    G = [set()] # graf w postaci listy zbiorów sąsiedztwa (operujemy na indeksach)

    Q = deque()
    Q.append(0)

    while Q:
        curr_id = Q.popleft()
        curr = state_list[curr_id]
        occupied = {(i, j) for (_, i, j) in curr}
        for idx, (kind, i, j) in enumerate(curr):
            moves = get_moves_for_kind(kind, i, j, N, M, allowed, occupied)
            for ni, nj in moves:
                new_state_list = list(curr)
                new_state_list[idx] = (kind, ni, nj)
                new_state_list.sort()
                new_state = tuple(new_state_list)
                if new_state not in state_to_id:
                    new_id = len(state_list)
                    state_to_id[new_state] = new_id
                    state_list.append(new_state)
                    G.append(set())
                    Q.append(new_id)
                else:
                    new_id = state_to_id[new_state]
                G[curr_id].add(new_id)
                G[new_id].add(curr_id)

    return G


def Edmonds(G : list[set[int]]) -> list[int]:
    # Zwraca listę match o długości n, gdzie match[v] to partner w matching'u lub None.
    n = len(G)
    match = [None] * n
    p = [None] * n
    base = list(range(n))
    used = [False] * n
    blossom = [False] * n

    def lca(a, b):
        nonlocal base, p, match
        used_lca = [False] * n
        while True:
            a = base[a]
            used_lca[a] = True
            if match[a] is None:
                break
            a = p[match[a]]
        while True:
            b = base[b]
            if used_lca[b]:
                return b
            b = p[match[b]]

    def markPath(v, b, x, q):
        nonlocal base, p, match, used, blossom
        while base[v] != b:
            blossom[base[v]] = blossom[base[match[v]]] = True
            p[v] = x
            x = match[v]
            if not used[x]:
                used[x] = True
                q.append(x)
            base[v] = base[x] = b
            v = p[x]

    def findPath(root):
        nonlocal used, p, base, match, blossom
        used[:] = [False] * n
        p[:] = [None] * n
        for i in range(n):
            base[i] = i
        q = deque()
        q.append(root)
        used[root] = True
        while q:
            v = q.popleft()
            for u in G[v]:
                if base[v] == base[u] or match[v] == u:
                    continue
                if u == root or (match[u] is not None and p[match[u]] is not None):
                    cur_lca = lca(v, u)
                    blossom[:] = [False] * n
                    markPath(v, cur_lca, u, q)
                    markPath(u, cur_lca, v, q)
                elif p[u] is None:
                    p[u] = v
                    if match[u] is None:
                        cur = u
                        while cur is not None:
                            pv = p[cur]
                            nxt = match[pv] if pv is not None else None
                            match[cur] = pv
                            match[pv] = cur
                            cur = nxt
                        return True
                    used[match[u]] = True
                    q.append(match[u])
        return False

    for v in range(n):
        if match[v] is None:
            findPath(v)
    return match


def my_solve(N, M, holes, pieces) -> bool:
    '''
    Rozwiązanie oparte na grafie stanów i maksymalnych skojarzeniach w ogólnym grafie
    (algorytm Edmonda).

    Parametry:
      N, M         - rozmiary planszy,
      holes        - lista pól niedostępnych,
      pieces       - lista pozycji figur, każda jako (kind, i, j)
                     (przy czym figury tego samego typu traktujemy jako nierozróżnialne;
                      stan reprezentujemy jako uporządkowaną krotkę).

    Zwraca:
      True, jeśli gracz rozpoczynający ma strategię wygrywającą,
      czyli gdy usunięcie stanu początkowego powoduje zmniejszenie rozmiaru maksymalnego matching'u;
      False w przeciwnym przypadku.
    '''
    G = build_graph_of_states(N, M, holes, pieces)
    n = len(G)
    
    # maksymalne skojarzenie w pełnym grafie
    full_matching = Edmonds(G)
    if full_matching[0] is None: return False # bo usunięcie stanu początkowego nic nie zmieni
    M_full = sum(1 for u in range(n) if full_matching[u] is not None) // 2
    if n % 2 == 0 and M_full == n // 2: return True # dla skojarzenia pełnego na pewno usunięcie "0" coś zmieni

    # maksymalne skojarzenie dla indukowanego podgrafu z usuniętym wierzchołkiem (stanem) początkowym
    # usuwamy z grafu połączenia z wierzchołka startowego
    for u in G[0]:
        G[u].discard(0)
    G[0] = []

    reduced_matching = Edmonds(G)
    M_red = sum(1 for u in range(n) if reduced_matching[u] is not None) // 2

    # jeżeli usunięcie stanu początkowego spowoduje spadek rozmiaru skojarzenia, to stan początkowy
    # jest krytyczny i gracz rozpoczynający wygrywa

    return M_red < M_full


runtests(my_solve)