QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#687916#7733. Cool, It’s Yesterday Four Times MorehamsterRE 0ms0kbPython31.8kb2024-10-29 21:53:052024-10-29 21:53:06

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 21:53:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-29 21:53:05]
  • 提交

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

output:


result: