Submission #59400018

Source Code Expand

H,W,K = map(int, input().split())

S = []
for _ in range(H):
    S.append(list(input()))

def is_movable(i,j):
    return (0 <= i <= H-1 and 0 <= j <= W-1) and S[i][j] == "."

visited = [[False] * W for _ in range(H)]
ans = 0

def dfs(i, j, k):
    global ans
    visited[i][j] = True
    for di,dj in [(-1,0), (1,0), (0,-1), (0,1)]:
        ni, nj = i+di, j+dj
        if is_movable(ni,nj) and not visited[ni][nj]:
            if k == K-1:
                ans += 1
            else:
                dfs(ni,nj,k+1)
    visited[i][j] = False

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            dfs(i, j, 0)

print(ans)

Submission Info

Submission Time
Task D - Count Simple Paths
User entropiajp
Language Python (PyPy 3.10-v7.3.12)
Score 425
Code Size 676 Byte
Status AC
Exec Time 659 ms
Memory 90316 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 35
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 02_handmade_01.txt, 02_handmade_02.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 57 ms 76536 KiB
00_sample_02.txt AC 56 ms 76588 KiB
00_sample_03.txt AC 227 ms 85044 KiB
01_random_01.txt AC 64 ms 81012 KiB
01_random_02.txt AC 566 ms 87720 KiB
01_random_03.txt AC 64 ms 81336 KiB
01_random_04.txt AC 58 ms 76676 KiB
01_random_05.txt AC 55 ms 76592 KiB
01_random_06.txt AC 253 ms 85452 KiB
01_random_07.txt AC 127 ms 84232 KiB
01_random_08.txt AC 57 ms 76456 KiB
01_random_09.txt AC 55 ms 76640 KiB
01_random_10.txt AC 115 ms 84816 KiB
01_random_11.txt AC 59 ms 81032 KiB
01_random_12.txt AC 148 ms 85256 KiB
01_random_13.txt AC 56 ms 76552 KiB
01_random_14.txt AC 142 ms 84440 KiB
01_random_15.txt AC 56 ms 76340 KiB
01_random_16.txt AC 211 ms 85648 KiB
01_random_17.txt AC 99 ms 83564 KiB
01_random_18.txt AC 92 ms 83200 KiB
01_random_19.txt AC 56 ms 76596 KiB
01_random_20.txt AC 64 ms 81192 KiB
01_random_21.txt AC 56 ms 76552 KiB
01_random_22.txt AC 62 ms 81080 KiB
01_random_23.txt AC 55 ms 76524 KiB
01_random_24.txt AC 63 ms 81156 KiB
01_random_25.txt AC 56 ms 76484 KiB
01_random_26.txt AC 105 ms 83324 KiB
01_random_27.txt AC 56 ms 76440 KiB
01_random_28.txt AC 57 ms 76404 KiB
01_random_29.txt AC 56 ms 76392 KiB
01_random_30.txt AC 80 ms 82104 KiB
02_handmade_01.txt AC 56 ms 76684 KiB
02_handmade_02.txt AC 659 ms 90316 KiB