Odporúčam pozrieť si bližšie info na tému Ford-Fulkersonov algoritmus pre tok v sieti. Pre správne pochopenie prikladám link: https://www.youtube.com/watch?v=Tl90tNtKvxs&ab_channel=MichaelSambol

Ak máš záujem o jednoduchý kód vy pythone:

from collections import deque

class MaxFlow:
def __init__(self, n):
self.n = n
self.graph = [[0] * n for _ in range(n)]
self.level = [-1] * n
self.iter = [0] * n

def add_edge(self, frm, to, cap):
self.graph[frm][to] += cap

def bfs(self, source):
self.level = [-1] * self.n
queue = deque([source])
self.level[source] = 0
while queue:
u = queue.popleft()
for v in range(self.n):
if self.graph[u][v] > 0 and self.level[v] < 0:
self.level[v] = self.level[u] + 1
queue.append(v)

def dfs(self, u, sink, flow):
if u == sink:
return flow
for i in range(self.iter[u], self.n):
self.iter[u] = i
v = i
if self.graph[u][v] > 0 and self.level[u] < self.level[v]:
d = self.dfs(v, sink, min(flow, self.graph[u][v]))
if d > 0:
self.graph[u][v] -= d
self.graph[v][u] += d
return d
return 0

def max_flow(self, source, sink):
flow = 0
INF = float('inf')
while True:
self.bfs(source)
if self.level[sink] < 0:
return flow
self.iter = [0] * self.n
f = self.dfs(source, sink, INF)
while f > 0:
flow += f
f = self.dfs(source, sink, INF)

def min_moves_to_remove_figures(board):
n = len(board)
source = 0
sink = n * n + 1
max_flow_solver = MaxFlow(n * n + 2)

def cell_id(x, y):
return x * n + y + 1

# Pridanie hrán zo zdroja do dolného radu
for j in range(n):
if board[n-1][j] == 0:
max_flow_solver.add_edge(source, cell_id(n-1, j), 1)

# Pridanie hrán medzi bunkami šachovnice podľa povolených pohybov
directions = [(-1, 0), (-1, -1), (-1, 1)]
for x in range(n):
for y in range(n):
if board[x][y] == 0:
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
max_flow_solver.add_edge(cell_id(x, y), cell_id(nx, ny), 1)

# Pridanie hrán z horného radu do ústia
for j in range(n):
if board[0][j] == 0:
max_flow_solver.add_edge(cell_id(0, j), sink, 1)

# Hľadanie maximálneho toku
max_flow = max_flow_solver.max_flow(source, sink)

# Kontrola, či sa všetky figúrky podarilo odstrániť
initial_figures = sum(1 for j in range(n) if board[n-1][j] == 0)
if max_flow == initial_figures:
return max_flow
else:
return -1

# Príklad použitia
board = [
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
]
print(min_moves_to_remove_figures(board)) # Očakávaný výstup závisí od konfigurácie boardu