結果
| 問題 |
No.1427 Simplified Tetris
|
| コンテスト | |
| ユーザー |
 tamato
|
| 提出日時 | 2021-03-12 23:29:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 244 ms / 2,000 ms |
| コード長 | 6,814 bytes |
| コンパイル時間 | 226 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 80,096 KB |
| 最終ジャッジ日時 | 2024-10-14 14:02:11 |
| 合計ジャッジ時間 | 5,311 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 37 |
ソースコード
mod = 1000000007
eps = 10**-9
def main():
import sys
import itertools
from collections import deque
import string
input = sys.stdin.readline
class Dinic:
def __init__(self, N):
self.N = N
self.adj = [[] for _ in range(N + 1)]
self.lv = None
self.progress = None
self.inf = 1 << 60
def add_edge(self, fr, to, cap):
# [to, cap, rev]
forward = [to, cap, None]
backward = forward[2] = [fr, 0, forward]
self.adj[fr].append(forward)
self.adj[to].append(backward)
def bfs(self, s, t):
que = deque([s])
lv = [-1] * (self.N + 1)
lv[s] = 0
while que:
v = que.popleft()
lvv = lv[v]
for u, cap, _ in self.adj[v]:
if cap and lv[u] == -1:
que.append(u)
lv[u] = lvv + 1
if u == t:
break
self.lv = lv
def dfs(self, s, t, flow):
st = deque([s])
st_f = deque([flow])
while st:
v = st[-1]
f = st_f[-1]
if v == t:
for i in range(len(st) - 1, 0, -1):
p = st[i - 1]
edge = self.adj[p][self.progress[p] - 1]
edge[1] -= f
edge[2][1] += f
v = p
return f
if self.progress[v] == len(self.adj[v]):
st.pop()
st_f.pop()
continue
else:
adj_v = self.adj[v]
for i in range(self.progress[v], len(adj_v)):
i = self.progress[v]
self.progress[v] = i + 1
u, cap, rev = adj_v[i]
if not cap or self.lv[u] != self.lv[v] + 1:
continue
else:
st.append(u)
st_f.append(min(st_f[-1], cap))
break
def max_flow(self, s, t):
flow = 0
while True:
self.bfs(s, t)
if self.lv[t] < 0:
return flow
self.progress = [0] * (self.N + 1)
flow_new = self.dfs(s, t, self.inf)
while flow_new:
flow += flow_new
flow_new = self.dfs(s, t, self.inf)
def fall(grid):
H, W = len(grid), len(grid[0])
grid_new = []
for h in range(H):
if grid[h] != "." * W:
grid_new.append(grid[h])
grid_new = ["." * W] * (H - len(grid_new)) + grid_new
return grid_new
H, W = map(int, input().split())
grid = []
for _ in range(H):
grid.append(input().rstrip('\n'))
grid_fallen = fall(grid)
for h in range(H):
for w in range(W):
if grid[h][w] != grid_fallen[h][w]:
print("No")
exit()
for h in range(H):
if grid[h] == "#" * W:
print("No")
exit()
empty_num = 0
for h in range(H):
if grid[h] == "." * W:
empty_num += 1
non_empty_num = H - empty_num
if W&1:
cnt = 0
for h in range(H):
for w in range(W):
if grid[h][w] == "#":
cnt += 1
if (cnt + empty_num)&1:
if empty_num == 0:
print("No")
exit()
empty_num -= 1
L = list(range(empty_num + non_empty_num))
for v in itertools.combinations(L, empty_num):
grid_new = []
v = set(v)
cnt = empty_num
if empty_num + non_empty_num != H:
cnt += 1
for i in range(empty_num + non_empty_num):
if i in v:
grid_new.append("#" * W)
else:
grid_new.append(grid[cnt])
cnt += 1
if empty_num + non_empty_num != H:
grid_new = ["." * W] + grid_new
grid_new_new = [["."] * W for _ in range(H)]
for h in range(H):
for w in range(W):
grid_new_new[h][w] = grid_new[h][w]
grid_new = grid_new_new
block_num = 0
for h in range(H):
for w in range(W):
if grid_new[h][w] == "#":
block_num += 1
if block_num & 1:
continue
block_num //= 2
D = Dinic(H * W + 2)
s = H * W + 1
t = H * W + 2
dhw = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for h in range(H):
for w in range(W):
if (h + w) % 2 == 0:
D.add_edge(s, h * W + w + 1, 1)
else:
D.add_edge(h * W + w + 1, t, 1)
if grid_new[h][w] == "#" and (h + w) % 2 == 0:
for dh, dw in dhw:
h_new, w_new = h + dh, w + dw
if 0 <= h_new < H and 0 <= w_new < W:
if grid_new[h_new][w_new] == "#":
D.add_edge(h * W + w + 1, h_new * W + w_new + 1, 1)
flow = D.max_flow(s, t)
abc = string.ascii_letters
i_abc = 0
if flow == block_num:
for h in range(H):
for w in range(W):
if (h + w) % 2 == 0:
hw = h * W + w + 1
for hw_new, cap, _ in D.adj[hw]:
if hw_new == s:
continue
if cap == 0:
h_new, w_new = divmod(hw_new - 1, W)
sss = abc[i_abc]
if h == h_new:
if w < w_new:
grid_new[h][w], grid_new[h][w_new] = sss, sss
else:
grid_new[h][w_new], grid_new[h][w] = sss, sss
else:
if h < h_new:
grid_new[h][w], grid_new[h_new][w] = sss, sss
else:
grid_new[h_new][w], grid_new[h][w] = sss, sss
i_abc += 1
print("Yes")
for h in range(H):
print("".join(grid_new[h]))
exit()
print("No")
if __name__ == '__main__':
main()