QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#687916 | #7733. Cool, It’s Yesterday Four Times More | hamster | RE | 0ms | 0kb | Python3 | 1.8kb | 2024-10-29 21:53:05 | 2024-10-29 21:53:06 |
answer
import sys
input = sys.stdin.read
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def p(x, y, n, m):
return (x + n - 1) * (2 * m - 1) + (y + m - 1)
def ck(x, y, n, m, a):
return 1 <= x <= n and 1 <= y <= m and a[x][y] == '.'
def dfs(x, y, n, m, a, vis):
stack = [(x, y, 0, 0)]
d = []
while stack:
x, y, DX, DY = stack.pop()
if vis[x][y]: continue
vis[x][y] = True
d.append((DX, DY))
for i in range(4):
tox, toy = x + dx[i], y + dy[i]
if ck(tox, toy, n, m, a) and not vis[tox][toy]:
stack.append((tox, toy, DX + dx[i], DY + dy[i]))
return d
def solve():
data = input().split()
idx = 0
T = int(data[idx])
idx += 1
results = []
for _ in range(T):
n = int(data[idx])
m = int(data[idx+1])
idx += 2
a = [list(data[idx + i]) for i in range(n)]
idx += n
vis = [[False] * (m + 1) for _ in range(n + 1)]
b = [set() for _ in range(n * m + 1)]
top = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i-1][j-1] == '.' and not vis[i][j]:
d = dfs(i, j, n, m, a, vis)
top += 1
for DX, DY in d:
b[top].add(p(DX, DY, n, m))
ans = 0
for i in range(1, top + 1):
unique = True
for j in range(1, top + 1):
if i != j and b[i].issubset(b[j]):
unique = False
break
ans += unique
results.append(ans)
for result in results:
print(result)
if __name__ == "__main__":
solve()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO