結果

問題 No.3807 Crossword Key with Cropping (Hard)
ユーザー kidodesu
提出日時 2026-11-14 16:27:46
言語 Codon
(0.20.6)
コンパイル:
codon build -release -exe -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 3,984 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,856 ms
コンパイル使用メモリ 484,420 KB
実行使用メモリ 55,648 KB
最終ジャッジ日時 2026-11-14 16:28:45
合計ジャッジ時間 57,897 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w = list(map(int, input().split()))
    S = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
    h += 2
    w += 2
    A = [0] * (h+1)*(w+1)
    B = [0] * (h+1)*(w+1)
    C = [0] * (h+1)*(w+1)
    D = [0] * (h+1)*(w+1)
    E = [0] * (h+1)*(w+1)
    F = [0] * (h+1)*(w+1)
    G = [0] * (h+1)*(w+1)
    H = [0] * (h+1)*(w+1)
    I = [0] * (h+1)*(w+1)
    J = [0] * (h+1)*(w+1)
    K = [0] * (h+1)*(w+1)
    W = w+1
    
    for y in range(1, h-1):
        for x in range(1, w-1):
            a0 = (y+1)*W+x+1
            a1 = (y+1)*W+x
            a2 = y*W+x+1
            a3 = y*W+x
            A[a0] += A[a1]+A[a2]-A[a3]
            B[a0] += B[a1]+B[a2]-B[a3]
            C[a0] += C[a1]+C[a2]-C[a3]
            D[a0] += D[a1]+D[a2]-D[a3]
            E[a0] += E[a1]+E[a2]-E[a3]
            F[a0] += F[a1]+F[a2]-F[a3]
            G[a0] += G[a1]+G[a2]-G[a3]
            H[a0] += H[a1]+H[a2]-H[a3]
            I[a0] += I[a1]+I[a2]-I[a3]
            J[a0] += J[a1]+J[a2]-J[a3]
            K[a0] += K[a1]+K[a2]-K[a3]
            s0, s1, s2, s3, s4 = S[y-1][x], S[y][x-1], S[y][x], S[y][x+1], S[y+1][x]
            if s2 == "#": continue
            if s0+s4 == "#." or s1+s3 == "#." or s0+s1+s3+s4 == "####":
                A[a0] += 1
            if s0+s4 == "#." or s3 == ".":
                B[a0] += 1
            if s0+s4 == "#.":
                C[a0] += 1
            if s1+s3 == "#." or s4 == ".":
                D[a0] += 1
            if s1+s3 == "#.":
                E[a0] += 1
            if s0+s3+s4 == "###":
                F[a0] += 1
            if s0+s1+s4 == "###":
                G[a0] += 1
            if s1+s3+s4 == "###":
                H[a0] += 1
            if s0+s1+s3 == "###":
                I[a0] += 1
            if s0+s4 == "##":
                J[a0] += 1
            if s1+s3 == "##":
                K[a0] += 1

    for _ in range(int(input())):
        y0, x0, y1, x1 = list(map(int, input().split()))
        y1, x1 = y1+1, x1+1
        ans = 0
        if 2 < min(y1-y0, x1-x0):
            ans += A[(y1-1)*W+x1-1]+A[(y0+1)*W+x0+1]-A[(y1-1)*W+x0+1]-A[(y0+1)*W+x1-1]
        if 2 < y1-y0:
            if 1 < x1-x0:
                ans += B[(y1-1)*W+x0+1]-B[(y1-1)*W+x0]-B[(y0+1)*W+x0+1]+B[(y0+1)*W+x0]
            ans += C[(y1-1)*W+x1]-C[(y1-1)*W+x1-1]-C[(y0+1)*W+x1]+C[(y0+1)*W+x1-1]
        if 2 < x1-x0:
            if 1 < y1-y0:
                ans += D[(y0+1)*W+x1-1]-D[y0*W+x1-1]-D[(y0+1)*W+x0+1]+D[y0*W+x0+1]
            ans += E[y1*W+x1-1]-E[(y1-1)*W+x1-1]-E[y1*W+x0+1]+E[(y1-1)*W+x0+1]

        if 1 < y1-y0 and 1 < x1-x0:
            if S[y0][x0]+S[y0][x0+1]+S[y0+1][x0] == ".##" or S[y0][x0]+S[y0][x0+1] == ".." or S[y0][x0]+S[y0+1][x0] == "..":
                ans += 1
            if S[y0][x1-1]+S[y0][x1-2]+S[y0+1][x1-1] == ".##" or S[y0][x1-1]+S[y0+1][x1-1] == "..":
                ans += 1
            if S[y1-1][x0]+S[y1-2][x0]+S[y1-1][x0+1] == ".##" or S[y1-1][x0]+S[y1-1][x0+1] == "..":
                ans += 1
            if S[y1-1][x1-1]+S[y1-2][x1-1]+S[y1-1][x1-2] == ".##":
                ans += 1
            ans += F[(y1-1)*W+x0+1]-F[(y1-1)*W+x0]-F[(y0+1)*W+x0+1]+F[(y0+1)*W+x0]
            ans += G[(y1-1)*W+x1]-G[(y1-1)*W+x1-1]-G[(y0+1)*W+x1]+G[(y0+1)*W+x1-1]
            ans += H[(y0+1)*W+x1-1]-H[y0*W+x1-1]-H[(y0+1)*W+x0+1]+H[y0*W+x0+1]
            ans += I[y1*W+x1-1]-I[(y1-1)*W+x1-1]-I[y1*W+x0+1]+I[(y1-1)*W+x0+1]
        elif 1 < y1-y0:
            if S[y0][x0] == ".":
                ans += 1
            if S[y1-2][x0]+S[y1-1][x0] == "#.":
                ans += 1
            ans += J[(y1-1)*W+x0+1]-J[(y1-1)*W+x0]-J[(y0+1)*W+x0+1]+J[(y0+1)*W+x0]
        elif 1 < x1-x0:
            if S[y0][x0] == ".":
                ans += 1
            if S[y0][x1-2]+S[y0][x1-1] == "#.":
                ans += 1
            ans += K[(y0+1)*W+x1-1]-K[y0*W+x1-1]-K[(y0+1)*W+x0+1]+K[y0*W+x0+1]
        else:
            if S[y0][x0] == ".":
                ans += 1
        print(ans)

main()
0