Submission #49502514

---

Source Code Expand

#再帰はCpython,その他はpypy
import sys
sys.setrecursionlimit(1000000)
from collections import deque


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

S = []

ans = 10 ** 6
S1 = [[] for _ in range(W)]

for i in range(H):
    tem = str(input())
    tem = list(tem)
    for j in range(W):
        S1[j].append(tem[j])
    S.append(tem)

#print(S)
#print(S1)

def check(l, zyougen):
    #print(zyougen)
    global ans
    que = deque()
    batu = 0
    maru = 0
    ten = 0
    #print(l)
    if len(l) < K:
        return 0
    else:
        for i in range(K):
            if l[i] == "x":
                batu += 1
            elif l[i] == "o":
                maru += 1
            elif l[i] == ".":
                ten += 1
            que.append(l[i])
        #print(que)
        if batu == 0:
            ans = min(ten, ans)
            #print(que, ans)

        for i in range(K,zyougen):
            #print(i)
            outt = que.popleft()
            inn = l[i]
            que.append(inn)

            if outt == "x":
                batu -= 1
            elif outt == "o":
                maru -= 1
            elif outt== ".":
                ten -= 1

            if inn == "x":
                batu += 1
            elif inn == "o":
                maru += 1
            elif inn == ".":
                ten += 1

            if batu == 0:
                ans = min(ten, ans)
                #print(ans, que)



for i in range(H):
    if W >= K:
        check(S[i],W)

for i in range(W):
    if H >= K:
        check(S1[i],H)

if ans == 10**6:
    print(-1)
else:
    print(ans)

Submission Info

Judge Result