76 lines
No EOL
1.6 KiB
Python
76 lines
No EOL
1.6 KiB
Python
import sys
|
|
|
|
sys.setrecursionlimit(25000)
|
|
input = sys.stdin.read().split()
|
|
|
|
h = int(input[0])
|
|
w = int(input[1])
|
|
cost_domino = int(input[2])
|
|
cost_square = int(input[3])
|
|
|
|
grid = []
|
|
idx = 4
|
|
for _ in range(h):
|
|
grid.append(input[idx])
|
|
idx += 1
|
|
|
|
free_count = 0
|
|
for r in range(h):
|
|
for c in range(w):
|
|
if grid[r][c] == '*':
|
|
free_count += 1
|
|
|
|
if cost_domino >= 2 * cost_square:
|
|
print(free_count * cost_square)
|
|
sys.exit()
|
|
|
|
nodes_left = []
|
|
nodes_right = []
|
|
left_id = {}
|
|
right_id = {}
|
|
|
|
for r in range(h):
|
|
for c in range(w):
|
|
if grid[r][c] == '*':
|
|
if (r + c) % 2 == 0:
|
|
left_id[(r, c)] = len(nodes_left) + 1
|
|
nodes_left.append((r, c))
|
|
else:
|
|
right_id[(r, c)] = len(nodes_right) + 1
|
|
nodes_right.append((r, c))
|
|
|
|
L = len(nodes_left)
|
|
R = len(nodes_right)
|
|
|
|
adj_list = [[] for _ in range(L + 1)]
|
|
|
|
dr = [-1, 1, 0, 0]
|
|
dc = [0, 0, -1, 1]
|
|
|
|
for r, c in nodes_left:
|
|
u = left_id[(r, c)]
|
|
for i in range(4):
|
|
nr, nc = r + dr[i], c + dc[i]
|
|
if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] == '*':
|
|
v = right_id[(nr, nc)]
|
|
adj_list[u].append(v)
|
|
|
|
assigned = [0] * (R + 1)
|
|
|
|
def match(node):
|
|
if seen[node]:
|
|
return False
|
|
seen[node] = True
|
|
for neighbor in adj_list[node]:
|
|
if assigned[neighbor] == 0 or match(assigned[neighbor]):
|
|
assigned[neighbor] = node
|
|
return True
|
|
return False
|
|
|
|
pairs_found = 0
|
|
for start in range(1, L + 1):
|
|
seen = [False] * (L + 1)
|
|
if match(start):
|
|
pairs_found += 1
|
|
ans = pairs_found * cost_domino + (free_count - 2 * pairs_found) * cost_square
|
|
print(ans) |