Paiza vol.2 (他の方のコードを読んでPythonで書いた)

gistfile1.py

import sys

if sys.version_info[0] < 3:
    input = raw_input
h, w = [int(e) for e in input().split()]

home = []
for _ in range(h):
    home.append([0 if c == '1' else 1 for c in input().rstrip()])
table = [[[c] + [0] * (h - 1) for c in line] for line in home]

accum = [[0] * (w + 1) for _ in range(h)]

for i in range(h):
    accum[0][table[i][0][0]] += 1
    for j in range(1, w):
        if table[i][j][0] > 0:
            table[i][j][0] += table[i][j - 1][0]
        accum[0][table[i][j][0]] += 1

for i in range(1, h):
    for j in range(w):
        for k in range(1, h):
            table[i][j][k] = min(table[i-1][j][k-1], table[i][j][k - 1])
            accum[k][table[i][j][k]] += 1

for i in range(h):
    for j in reversed(range(w)):
        accum[i][j] += accum[i][j + 1]

for _ in range(int(input())):
    height, width = [int(e) for e in input().split()]
    if height <= h and width <= w:
        print(accum[height - 1][width])
    else:
        print(0)