A solution for paiza online hackathon Vol.2 https://paiza.jp/poh/paizen

poh2.php

<?php
fscanf(STDIN, '%d%d', $h, $w);
for ($i = 0; $i < $h; $i++) {
    $rawMap[] = fgets(STDIN);
}

for ($y = 0; $y < $h; $y++) {
    $width = 0;
    for ($x = $w - 1; $x >= 0; $x--) {
        if ($rawMap[$y][$x] == '0') {
            $map[$y][$x] = ++$width;
        } else {
            $map[$y][$x] = $width = 0;
        }
    }
}
for ($x = 0; $x < $w; $x++) {
    $map[$h][$x] = 0;
}

$start = array();
$last = 0;
for ($x = 0; $x < $w; $x++) {
    for ($y = 0; $y < $h + 1; $y++) {
        $width = $map[$y][$x];
        for ($i = $width + 1; $i <= $last; $i++) {
            $height = $y - $start[$i];
            if (isset($preCount[$i][$height])) {
                $preCount[$i][$height]++;
            } else {
                $preCount[$i][$height] = 1;
            }
        }
        for ($i = $last + 1; $i <= $width; $i++) {
            $start[$i] = $y;
        }
        $last = $width;
    }
}

$count = array();
foreach ($preCount as $width => $heightCounts) {
    foreach ($heightCounts as $height => $cnt) {
        for ($y = 1; $y <= $height; $y++) {
            if (isset($count[$width][$y])) {
                $count[$width][$y] += ($height - $y + 1) * $cnt;
            } else {
                $count[$width][$y] = ($height - $y + 1) * $cnt;
            }
        }
    }
}

fgets(STDIN);
$data = stream_get_contents(STDIN);
echo preg_replace_callback(
    '/([0-9]+) ([0-9]+)/S',
    function($m) use ($count) {
        return isset($count[$m[2]][$m[1]]) ? $count[$m[2]][$m[1]] : 0;
    },
    $data
);