結果

問題 No.3807 Crossword Key with Cropping (Hard)
ユーザー kidodesu
提出日時 2026-11-14 16:12:26
言語 Codon
(0.20.6)
コンパイル:
codon build -release -exe -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 4,331 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,599 ms
コンパイル使用メモリ 487,256 KB
実行使用メモリ 71,092 KB
最終ジャッジ日時 2026-11-14 16:13:58
合計ジャッジ時間 65,319 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_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 for x in range(w+1)] for y in range(h+1)]
    B = [[0 for x in range(w+1)] for y in range(h+1)]
    C = [[0 for x in range(w+1)] for y in range(h+1)]
    D = [[0 for x in range(w+1)] for y in range(h+1)]
    E = [[0 for x in range(w+1)] for y in range(h+1)]
    F = [[0 for x in range(w+1)] for y in range(h+1)]
    G = [[0 for x in range(w+1)] for y in range(h+1)]
    H = [[0 for x in range(w+1)] for y in range(h+1)]
    I = [[0 for x in range(w+1)] for y in range(h+1)]
    J = [[0 for x in range(w+1)] for y in range(h+1)]
    K = [[0 for x in range(w+1)] for y in range(h+1)]
    
    for y in range(1, h-1):
        for x in range(1, w-1):
            A[y+1][x+1] += A[y+1][x]+A[y][x+1]-A[y][x]
            B[y+1][x+1] += B[y+1][x]+B[y][x+1]-B[y][x]
            C[y+1][x+1] += C[y+1][x]+C[y][x+1]-C[y][x]
            D[y+1][x+1] += D[y+1][x]+D[y][x+1]-D[y][x]
            E[y+1][x+1] += E[y+1][x]+E[y][x+1]-E[y][x]
            F[y+1][x+1] += F[y+1][x]+F[y][x+1]-F[y][x]
            G[y+1][x+1] += G[y+1][x]+G[y][x+1]-G[y][x]
            H[y+1][x+1] += H[y+1][x]+H[y][x+1]-H[y][x]
            I[y+1][x+1] += I[y+1][x]+I[y][x+1]-I[y][x]
            J[y+1][x+1] += J[y+1][x]+J[y][x+1]-J[y][x]
            K[y+1][x+1] += K[y+1][x]+K[y][x+1]-K[y][x]
            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 s0+s2+s4 == "#.." or s1+s2+s3 == "#.." or s0+s1+s2+s3+s4 == "##.##":
                A[y+1][x+1] += 1
            if s0+s2+s4 == "#.." or s2+s3 == "..":
                B[y+1][x+1] += 1
            if s0+s2+s4 == "#..":
                C[y+1][x+1] += 1
            if s1+s2+s3 == "#.." or s2+s4 == "..":
                D[y+1][x+1] += 1
            if s1+s2+s3 == "#..":
                E[y+1][x+1] += 1
            if s0+s2+s3+s4 == "#.##":
                F[y+1][x+1] += 1
            if s0+s1+s2+s4 == "##.#":
                G[y+1][x+1] += 1
            if s1+s2+s3+s4 == "#.##":
                H[y+1][x+1] += 1
            if s0+s1+s2+s3 == "##.#":
                I[y+1][x+1] += 1
            if s0+s2+s4 == "#.#":
                J[y+1][x+1] += 1
            if s1+s2+s3 == "#.#":
                K[y+1][x+1] += 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][x1-1]+A[y0+1][x0+1]-A[y1-1][x0+1]-A[y0+1][x1-1]
        if 2 < y1-y0:
            if 1 < x1-x0:
                ans += B[y1-1][x0+1]-B[y1-1][x0]-B[y0+1][x0+1]+B[y0+1][x0]
            ans += C[y1-1][x1]-C[y1-1][x1-1]-C[y0+1][x1]+C[y0+1][x1-1]
        if 2 < x1-x0:
            if 1 < y1-y0:
                ans += D[y0+1][x1-1]-D[y0][x1-1]-D[y0+1][x0+1]+D[y0][x0+1]
            ans += E[y1][x1-1]-E[y1-1][x1-1]-E[y1][x0+1]+E[y1-1][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][x0+1]-F[y1-1][x0]-F[y0+1][x0+1]+F[y0+1][x0]
            ans += G[y1-1][x1]-G[y1-1][x1-1]-G[y0+1][x1]+G[y0+1][x1-1]
            ans += H[y0+1][x1-1]-H[y0][x1-1]-H[y0+1][x0+1]+H[y0][x0+1]
            ans += I[y1][x1-1]-I[y1-1][x1-1]-I[y1][x0+1]+I[y1-1][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][x0+1]-J[y1-1][x0]-J[y0+1][x0+1]+J[y0+1][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][x1-1]-K[y0][x1-1]-K[y0+1][x0+1]+K[y0][x0+1]
        else:
            if S[y0][x0] == ".":
                ans += 1
        print(ans)

main()
0