Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. At first, all cells were painted white.

Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.

Compute the following:

For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

Constraints

3 \leq H \leq 10^9

3 \leq W \leq 10^9

0 \leq N \leq min(10^5,H×W)

1 \leq a_i \leq H (1 \leq i \leq N)

1 \leq b_i \leq W (1 \leq i \leq N)

(a_i, b_i) \neq (a_j, b_j) (i \neq j)

Input

The input is given from Standard Input in the following format:

H W N
a_1 b_1
:
a_N b_N

Output

Print 10 lines.
The (j+1)-th ( 0 \leq j \leq 9 ) line should contain the number of the subrectangles of size 3×3 of the grid that contains exactly j black cells.

Sample Input 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

Sample Output 1

0
0
0
2
4
0
0
0
0
0

There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.

Sample Input 2

10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9

Sample Output 2

4
26
22
10
2
0
0
0
0
0

Sample Input 3

1000000000 1000000000 0

Sample Output 3

999999996000000004
0
0
0
0
0
0
0
0
0



Sample input:
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4


Sample output:
0
0
0
2
4
0
0
0
0
0

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    H, W, N = map(int, sys.stdin.readline().split())
    nb = [0] * 10
    dx = (1, 0, -1, 0, 1, 1, -1, -1)
    dy = (0, 1, 0, -1, 1, -1, 1, -1)
    bb = []

    for lp in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1

        if in_field(H, W, a, b):
            bb.append((a,b))

        for i in range(len(dx)):
            if in_field(H, W, a+dx[i], b+dy[i]):
                bb.append((a+dx[i], b+dy[i]))

    bb.sort()
    cnt = 1

    for i, box in enumerate(bb):
        if i == 0:
            continue
        if box != bb[i-1]:
            nb[cnt] += 1
            cnt = 1
        else:
            cnt += 1

    nb[cnt] += 1

    nb[0] = (W-2)*(H-2) - sum(nb)

    print(*nb, sep='\n')

def in_field(H, W, a, b):
    return (1 <= a <= H-2) and (1 <= b <= W-2)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

h, w, n = map(int, input().split())
hs, ws = h-2, w-2

dd = defaultdict(int)

for a, b in (map(int, input().split()) for _ in range(n)):
	for y in range(max(0, a-3), min(a, hs)):
		for x in range(max(0, b-3), min(b, ws)):
			dd[(y,x)] += 1

c = Counter(dd.values())

for i in range(1,10):
	print(c[i] if i in c else 0)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

h, w, n = map(int, input().split())
blacks = defaultdict(int)

for a, b in (map(int, input().split()) for _ in range(n)):
    for p in range(max(0, a - 3), min(a, h - 2)):
        for q in range(max(0, b - 3), min(b, w - 2)):
            blacks[(p, q)] += 1

print ((h - 2) * (w - 2) - len(blacks))

count = Counter(blacks.values())
for i in range(10):
    print(count[i] if i in count else 0)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

h, w, n = map(int, input().split())
blacks = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    for p in range(max(0, a - 3), min(a, h - 2)):
        for q in range(max(0, b - 3), min(b, w - 2)):
            blacks[(p, q)] += 1

count = Counter(blacks.values())
for i in range(10):
    print(count[i] if i in count else 0)

Submission status: Wrong Answer

Solution code:
w,h,n = map(int,input().split())
l = {1:0, 2:w, 3:0, 4:h}
for _ in range(n):
    x,y,a = map(int,input().split())
    if a == 1:
        l[a] = max(l[a], x) 
    elif a == 2:
        l[a] = min(l[a], x) 
    elif a == 3:
        l[a] = max(l[a], y) 
    elif a == 4:
        l[a] = min(l[a], y)
        
if l[2]-l[1] <=0 or l[4]-l[3]<=0:
    print(0)
else : print((l[2]-l[1])*(l[4]-l[3]))

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W, N = 0, 0, 0
filled = {}

def boundary_check(pos):
    """
    (x, y) -> bool
    """
    return pos[0] < W - 2 and pos[1] < H - 2 and pos[0] >= 0 and pos[1] >= 0

def matrix_cell_in(a, b):
    """
    int -> int -> (int, int)

    塗りつぶされたセルの座標から、そのセルが含まれる 3 * 3 連続セルの集合を返す。
    3 * 3 連続セルは左上セルの座標で表現する。
    """
    matrixes = list(product(range(a-2,a+1),(range(b-2, b+1))))
    return list(filter(boundary_check ,matrixes))
    # return matrixes

def fill(pos, cell):
    """
    (int, int) -> unit

    3 * 3連続セルの座標を受け取って、その中の黒マスの数を増やす。まだ塗られていなかった場合は 1 にする。
    """
    if pos in filled:
        filled[pos] += 1
    else:
        filled[pos] = 1


H, W, N = map(int, input().split(" "))

for i in range(N):
    b, a = map(int, input().split(" "))
    a, b = a-1, b-1
    for cell in matrix_cell_in(a,b):
        fill(cell, (a,b))

results = [0 for _ in range(10)]
for v in filled.values():
    results[v] += 1

for r in results:
    print(r)

Submission status: Wrong Answer

Solution code:
F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*10
for Y,X in S:
	for A in range(9):
		A,B=X+A%3-1,Y+A//3-1
		if 0<A<W-1 and 0<B<H-1 and(A,B)not in T:
			T.add((A,B));Q=0
			for C in range(9):Q+=(B+C//3,A+C%3)in S
			Z[Q]+=1
print(*Z,sep='\n')

Submission status: Wrong Answer

Solution code:
F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*9
for Y,X in S:
	for A in range(9):
		A,B=X+A%3-1,Y+A//3-1
		if 0<A<W-1 and 0<B<H-1 and(A,B)not in T:
			T.add((A,B));Q=0
			for C in range(9):Q+=(B+C//3,A+C%3)in S
			Z[Q]+=1
print(*Z,sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

h, w, n = map(int, input().split())
dd = defaultdict(int)

for a, b in (map(int, input().split()) for _ in range(n)):
    for y in range(max(0, a - 3), min(a, h - 2)):
        for x in range(max(0, b - 3), min(b, w - 2)):
            dd[(y, x)] += 1

c = Counter(dd.values())
for i in range(10):
    print(c[i] if i in c else 0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    H, W, N = map(int, input().split())

    d = defaultdict(int)
    for _ in range(N):
        a, b = map(int, input().split())
        for y in range(-2, 1):
            for x in range(-2, 1):
                n_y, n_x = y + a, x + b
                if 0 < n_y <= H - 2 and 0 < n_x <= W - 2:
                    d[(n_y, n_x)] += 1

    ans = [0] * 10
    for k, v in d.items():
        ans[v] += 1

    print(*ans, sep="\n")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class board:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.pieces = self.make_pieces()
        self.results = dict()

    def make_pieces(self):
        pieces = []
        for i in range(self.h):
            for j in range(self.w):
                pieces.append(0)
        return pieces

    def draw(self, i, j):
        i -= 1; j-= 1

        index = j + i * self.w
        self.pieces[index] = 1

    def start_scan(self):
        for i in range(self.w - 2):
            for j in range(self.h - 2):
                num = 0
                for x in range(i, i+3):
                    for y in range(j, j+3):
                        index = x + y * self.w
                        v = self.pieces[index]
                        if v == 1:
                            num += 1
                self.results[num] = num

    def searched_box(self, num):
        return self.results.get(num, 0)
        

if __name__ == '__main__':
    args = input().split(' ')
    board_h = int(args[0])
    board_w = int(args[1])
    n       = int(args[2])

    board = board(board_h, board_w)
    for _ in range(n):
        args = input().split(' ')
        i = int(args[0])
        j = int(args[1])
        board.draw(i, j)

    board.start_scan()
    for i in range(10):
        print(board.searched_box(i))

Submission status: Wrong Answer

Solution code:
import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap=[]

#print(board)
for i in range(0,N):
    a, b = list(map(int, input().split()))
    for j in range(a-1, a+2):
        for k in range(b-1, b+2):
            if j>1 and j<H and k>1 and k<W:
                rectmap.append([j-1, k-1])
#print(rectmap)
#rectmap.sort()
rectmap.append([])
while len(rectmap)!=1 :
#    print(rectmap[0])
#    print(rectmap)
    c=0
#    print(rectmap)
    while rectmap[0]==rectmap[1]:
        c+=1
        rectmap.pop(0)
    c+=1
    rectmap.pop(0)
#    print(rectmap)
#    input()
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Wrong Answer

Solution code:
h, w, n = map(int, raw_input().split())
a = [map(int, raw_input().split()) for i in range(n)]

m = [[0 for i in range(w)] for j in range(h)]

for i in range(n):
    m[a[i][0]-1][a[i][1]-1] = 1

count = [0] * n

for i in range(h-2):
        for j in range(w-2):
            kuro = 0
            for s in range(3):
                for t in range(3):
                    kuro += m[i+s][j+t]
            count[kuro] += 1

for i in range(n):
    print count[i]

Submission status: Wrong Answer

Solution code:
h, w, n = map(int, raw_input().split())
a = [map(int, raw_input().split()) for i in range(n)]

m = [[0 for i in range(w)] for j in range(h)]

for i in range(n):
    m[a[i][0]-1][a[i][1]-1] = 1

count = [0] * n

for i in range(h-2):
        for j in range(w-2):
            kuro = 0
            for s in range(3):
                for t in range(3):
                    kuro += m[i+s][j+t]
            count[kuro-1] += 1

for i in range(n):
    print count[i]

Submission status: Wrong Answer

Solution code:
#coding:utf-8

# 升目の高さ、幅、塗りつぶし回数
height, width, n = map(int,raw_input().split())

if n == 0:
	for i in xrange(10):
		print 0

# 升目の生成処理
mass = [[] for i in xrange(height)]

# 升目の塗りつぶし処理
for i in xrange(n):
	a, b = map(int, raw_input().split())
	if len(mass[a-1]) < b-1:
		for i in xrange(b-2-len(mass[a-1])+1):
			mass[a-1].append(0)
	mass[a-1].append(1)

# jとresultを定義
j = [0]*10
result = 0

# 塗りつぶした升目をカウント
for y in xrange(height-2):
	for x in xrange(width-2):
		for n_y in xrange(y,y+3):
			for n_x in xrange(x,x+3):
				try:
					result = result + mass[n_y][n_x]
				except:
					pass
		j[result] = j[result]+1
		result = 0

for i in j:
	print i

# 
# mass = [[0 for i in xrange(width)] for j in xrange(height)]
# for list_ in mass:
# 	print list_
# j = [0]*10

# for i in xrange(n):
# 	y, x = map(int,raw_input().split())
# 	mass[y-1][x-1] = 1
# 	for list_ in mass:
# 		print list_

# result = 0
# for x in xrange(width-2):
# 	for y in xrange(height-2):
# 		for n_x in xrange(x,x+3):
# 			for n_y in xrange(y,y+3):
# 				result = result + mass[n_y][n_x]
# 		j[result] = j[result]+1
# 		result = 0

# for i in j:
# 	print i

Submission status: Wrong Answer

Solution code:
#coding:utf-8

# 升目の高さ、幅、塗りつぶし回数
height, width, n = map(int,raw_input().split())

if n == 0:
	for i in xrange(10):
		print 0

# 升目の生成処理
mass = [[] for i in xrange(height)]

# 升目の塗りつぶし処理
for i in xrange(n):
	a, b = map(int, raw_input().split())
	if len(mass[a-1]) < b-1:
		for i in xrange(b-2-len(mass[a-1])+1):
			mass[a-1].append(0)
	mass[a-1].append(1)

# jとresultを定義
j = [0]*10
result = 0

# 塗りつぶした升目をカウント
for y in xrange(height-2):
	for x in xrange(width-2):
		for n_y in xrange(y,y+3):
			for n_x in xrange(x,x+3):
				try:
					result = result + mass[n_y][n_x]
				except:
					pass
		j[result] = j[result]+1
		result = 0

print j

# 
# mass = [[0 for i in xrange(width)] for j in xrange(height)]
# for list_ in mass:
# 	print list_
# j = [0]*10

# for i in xrange(n):
# 	y, x = map(int,raw_input().split())
# 	mass[y-1][x-1] = 1
# 	for list_ in mass:
# 		print list_

# result = 0
# for x in xrange(width-2):
# 	for y in xrange(height-2):
# 		for n_x in xrange(x,x+3):
# 			for n_y in xrange(y,y+3):
# 				result = result + mass[n_y][n_x]
# 		j[result] = j[result]+1
# 		result = 0

# for i in j:
# 	print i

Submission status: Wrong Answer

Solution code:
h,w,n=map(int,input().split())
s={tuple(map(int,input().split())) for _ in range(n)}
t={(a+p,b+q) for a,b in s for p in range(-2,3) for q in range(-2,3)}
j=[0]*10
for a,b in t:
    if 2<=a<=h-1 and 2<=b<=w-1:
        j[sum((a+p,b+q) in s for p in range(-1,2) for q in range(-1,2))]+=1
for c in j:
    print (c)

Submission status: Wrong Answer

Solution code:
class nSnukes_Coloring:
	def returnEachNumber(self,H,W,N,r):
		HWMap = [[0 for i in range(W+2)] for j in range(H+2)]
		points = [0 for i in range(10)]
		for cord in range(len(r)):
			y,x = r[cord][0],r[cord][1]
			for i in range(3):
				for j in range(3):
					HWMap[y-i+1][x-j+1] += 1
		for i in range(H-2):
			for j in range(W-2):
				points[HWMap[i+2][j+2]] += 1
		for i in range(len(points)):
			print points[i]

if __name__ == "__main__":
	H, W, N = map(int, raw_input().split())
	if N == 0:
		l = [0 for i in range(10)]
		for i in range(10):
			print l[i]
	else:
		r = [[int(i) for i in raw_input().split()] for j in range(N)]
		s = nSnukes_Coloring()
		s.returnEachNumber(H,W,N,r)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, N = list(map(int,input().split()))
counts = np.zeros(10,dtype=int)
if N == 0:
    for jdx in range(10):
        print( counts[jdx] )
    quit()
A = [0] * N
B = [0] * N
M = np.zeros((H,W), dtype=int)
for idx in range(N):
    A[idx], B[idx] = list(map(int,input().split()))
    M[A[idx]-1,B[idx]-1] = 1

tmp1 = M[0:H-2].copy()
tmp2 = M[1:H-1].copy()
tmp3 = M[2:H].copy()
M2 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M3 = M2.T.copy()
tmp1 = M3[0:W-2].copy()
tmp2 = M3[1:W-1].copy()
tmp3 = M3[2:W].copy()
M4 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M5 = M4.ravel()
remain = (H-2)*(W-2)
for jdx in range(10):
    M5 = M5[M5>jdx]
    counts[jdx] = remain - M5.size
    remain = M5.size

for jdx in range(10):
    print( counts[jdx] )

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, N = list(map(int,input().split()))
counts = np.zeros(9,dtype=int)
if N == 0:
    for jdx in range(9):
        print( counts[jdx] )
    quit()
A = [0] * N
B = [0] * N
M = np.zeros((H,W), dtype=int)
for idx in range(N):
    A[idx], B[idx] = list(map(int,input().split()))
    M[A[idx]-1,B[idx]-1] = 1

tmp1 = M[0:H-2].copy()
tmp2 = M[1:H-1].copy()
tmp3 = M[2:H].copy()
M2 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M3 = M2.T.copy()
tmp1 = M3[0:W-2].copy()
tmp2 = M3[1:W-1].copy()
tmp3 = M3[2:W].copy()
M4 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M5 = M4.ravel()
remain = (H-2)*(W-2)
for jdx in range(9):
    M5 = M5[M5>jdx]
    counts[jdx] = remain - M5.size
    remain = M5.size

for jdx in range(9):
    print( counts[jdx] )

Submission status: Wrong Answer

Solution code:
def read_nums():
    return map(int, raw_input().split(' '))


def is_in_the_map(x, y):
    return x < H-1 and x > 0 and y < W-1 and y > 0


def solve():
    res = [0 for _ in range(N)]
    for i in range(N):
        a = As[i]
        b = Bs[i]
        for j in [-1, 0, 1]:
            for k in [-1, 0, 1]:
                x_mid = a + j
                y_mid = b + k
                if not is_in_the_map(x_mid, y_mid) or memo[x_mid][y_mid] == 1:
                    continue
                memo[x_mid][y_mid] = 1
                count = 0
                for x_pad in [-1, 0, 1]:
                    for y_pad in [-1, 0, 1]:
                        x = x_mid + x_pad
                        y = y_mid + y_pad
                        if Map[x][y] == 1:
                            count += 1
                res[count] += 1
    res[0] = (H-2) * (W-2) - sum(res)
    return res


H, W, N = read_nums()
As = [0 for _ in range(N)]
Bs = [0 for _ in range(N)]
Map = [[0 for _ in range(W)] for _ in range(H)]
for i in range(N):
    a, b = read_nums()
    As[i] = a - 1
    Bs[i] = b - 1
    Map[a - 1][b - 1] = 1
memo = [[0 for _ in range(W)] for _ in range(H)]
res = solve()
for i in res:
    print i

Submission status: Wrong Answer

Solution code:
def read_nums():
    return map(int, raw_input().split(' '))


def is_in_the_map(x, y):
    return x < H-1 and x > 0 and y < W-1 and y > 0


def solve():
    res = [0 for _ in range(N)]
    for i in range(N):
        a = As[i]
        b = Bs[i]
        for j in [-1, 0, 1]:
            for k in [-1, 0, 1]:
                x_mid = a + j
                y_mid = b + k
                if not is_in_the_map(x_mid, y_mid) or memo[x_mid][y_mid] == 1:
                    continue
                memo[x_mid][y_mid] = 1
                count = 0
                for x_pad in [-1, 0, 1]:
                    for y_pad in [-1, 0, 1]:
                        x = x_mid + x_pad
                        y = y_mid + y_pad
                        if Map[x][y] == 1:
                            count += 1
                res[count] += 1
    res[0] = (H-2) * (W-2) - sum(res)
    return res


H, W, N = read_nums()
As = [0 for _ in range(N)]
Bs = [0 for _ in range(N)]
Map = [[0 for _ in range(W)] for _ in range(H)]
for i in range(N):
    a, b = read_nums()
    As[i] = a - 1
    Bs[i] = b - 1
    Map[a - 1][b - 1] = 1
As, Bs = zip(*sorted(zip(As, Bs), key=lambda x: (x[0], x[1])))
memo = [[0 for _ in range(W)] for _ in range(H)]
res = solve()
for i in res:
    print i

Submission status: Wrong Answer

Solution code:
def solve():
    w, h, n = [int(i) for i in input().split()]
    dic = dict()
    for i in range(n):
        a, b = map(lambda x: int(x) - 1, input().split())
        for j in range(3):
            for k in range(3):
                aj = a + j - 1
                bk = b + k - 1
                if 0 < aj and aj < w - 1 and 0 < bk and bk < h - 1:
                    print("DEBUG", aj, bk)
                    if (aj, bk) in dic:
                        dic[(aj, bk)] += 1
                    else:
                        dic[(aj, bk)] = 1
    ans = [0 for i in range(10)]
    for v in dic.values():
        ans[v] += 1
    for i in range(10):
        if i == 0:
            print((w - 2) * (h - 2) - sum(ans))
        else:
            print(ans[i])


if __name__=="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def inside(x, y):    
    return 0 <= x <= h - 3 and 0 <= y <= w - 3

h, w, n = (int(_) for _ in input().split())
black = defaultdict(int)
for i in range(n):
    a, b = (int(_) - 1 for _ in input().split())
    for j in range(3):
        for k in range(3):
            x, y = a - j, b - k
            if not inside(x, y):
                continue
            black[(x, y)] += 1
ans = [0 for i in range(10)]
ans[0] = (h-2)*(w-2)
for k in black:
    ans[black[k]] += 1
for i in range(10):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def inside(x, y):    
    return 0 <= x <= h - 3 and 0 <= y <= w - 3

h, w, n = (int(_) for _ in input().split())
black = defaultdict(int)
for i in range(n):
    a, b = (int(_) - 1 for _ in input().split())
    for j in range(3):
        for k in range(3):
            x, y = a - j, b - k
            if not inside(x, y):
                continue
            black[(x, y)] += 1
ans = defaultdict(int)
ans[0] = (h-2)*(w-2)
for k in black:
    ans[black[k]] += 1
for i in range(10):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def inside(x, y):    
    return 0 <= x <= h - 3 and 0 <= y <= w - 3

h, w, n = (int(_) for _ in input().split())
black = defaultdict(int)
for i in range(n):
    a, b = (int(_) - 1 for _ in input().split())
    for j in range(3):
        for k in range(3):
            x, y = a - j, b - k
            if not inside(x, y):
                continue
            black[(x, y)] += 1
ans = defaultdict(int)
ans[0] = (h-2)*(w-2)
for k in black:
    ans[black[k]] += 1
for i in range(10):
    print(i, ans[i])

Submission status: Wrong Answer

Solution code:
H, W, N = map(int, raw_input().split())
dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
board = {}

for i in xrange(N):
    a, b = map(int, raw_input().split())
    for j in xrange(9):
        x, y = a+dx[j], b+dy[j]
        if x <= 1 or x >= H or y <= 1 or y >= W:
            continue
        if (x, y) in board:
            board[(x, y)] += 1
        else:
            board[(x, y)] = 1
ans = [0] * 10
for v in board.values():
    ans[v] += 1
for a in ans:
    print a

Submission status: Wrong Answer

Solution code:
H, W, N = map(int, raw_input().split())
dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
board = {}

for i in xrange(N):
    a, b = map(int, raw_input().split())
    for j in xrange(9):
        x, y = a+dx[j], b+dy[j]
        if x <= 1 or x >= H or y <= 1 or y >= W:
            continue
        if (x, y) in board:
            board[(x, y)] += 1
        else:
            board[(x, y)] = 1
ans = [0] * 10
for v in board.values():
    if v > 0:
        ans[v] += 1
for a in ans:
    print a

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
def scan(sx, sy, mp):
    cnt = 0
    for y in range(sy, sy + 3):
        for x in range(sx, sx + 3):
            if mp[y][x] == 1:
                cnt += 1
    return cnt

H, W, N = map(int, input().split())
mp = [[0 for i in range(W)] for j in range(H)]
input_ls = []
for i in range(N):
    a, b = map(int, input().split())
    input_ls.append((a,b))
    mp[a-1][b-1] = 1
    
print(mp, input_ls)

ans_list = [0 for i in range(10)]

sx = 0
sy = 0
for y in range(H-2):
    for x in range(W-2):
        sx = x
        sy = y
        cnt = scan(sx, sy, mp)
        ans_list[cnt] += 1
print(ans_list)

Submission status: Wrong Answer

Solution code:
h, w, n = map(int, raw_input().split())

black = {}
for i in range(n):
    a, b = map(int, raw_input().split())
    grid = [(x, y) for y in range(max(1, a-1), min(a+2, h+1))
                   for x in range(max(1, b-1), min(b+2, w+1))]
    for key in grid:
        x, y = key
        if 1 < x < w and 1 < y < h:
            if key in black:
                black[key] += 1
            else:
                black[key] = 1
            
count = [0] * 10

z = (h-2)*(w-2) - len(black)
count[0] = z if 0 < z < 10 else 0

for v in black.values():
    if v < 10:
        count[v] += 1
        
for c in count:
    print c

Submission status: Wrong Answer

Solution code:
from collections import Counter
h, w, n = [int(i) for i in input().split()]
cnt = Counter()

vs = []
for i in range(-1, 2):
	for j in range(-1, 2):
		vs.append((i,j))

print(list(vs))
for _ in range(n):
	a, b = [int(i) for i in input().split()]
	for v in vs:
		aa = a + v[0]
		bb = b + v[1]
		if 2<=aa<=h-1 and 2<=bb<=w-1:
			cnt.update([(aa, bb)])


print(cnt)

cnt2 = [0] * 10
for k in cnt:
	c = cnt[k]
	cnt2[c] += 1

for i in cnt2:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


H, W, N = MAP()
 
ab = [LIST() for _ in range(N)]
 
dic = defaultdict(int)
for a, b in ab:
	dic[str(a)+"_"+str(b)] = 1
 
check = defaultdict(int)
 
def count_black(Y, X):
	cnt = 0
	if 3 <= Y and 3 <= X:
		for i in range(3):
			for j in range(3):
				if dic[str(Y-i)+"_"+str(X-j)]:
					cnt += 1
		if cnt:
			ans[cnt] += 1
 
 
ans = [0]*10
for y, x in ab:
	for i in range(3):
		for j in range(3):
			if y+i <= H and x+j <= W and check[str(y+i)+"_"+str(x+j)] == 0:
				count_black(y+i, x+j)
				check[str(y+i)+"_"+str(x+j)] = 1
 
ans[0] = (H-2)*(W-2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
black=[tuple(map(int,input().split())) for _ in range(n)]
sblack=set(black)
ans=[0]*10
for a,b in black:
    for x in range(3):
        for y in range(3):
            cnt=0
            ok=True
            for nx,ny in [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]:
                dx,dy=nx-x,ny-y
                if 1<=a-dx<=h and 1<=b-dy<=w:
                    if (a-dx,b-dy) in sblack:
                        cnt+=1
                else:
                    ok=False
                    break
            if ok:
                ans[cnt]+=1
for i in range(1,10):
    ans[i]//=i
ans[0]=(h-2)*(w-2)-sum(ans[1:])
for num in ans:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W, N = MAP()

ab = [LIST() for _ in range(N)]

dic = defaultdict(int)
for a, b in ab:
	dic[(a, b)] = 1

check = defaultdict(int)

def count_black(Y, X):
	cnt = 0
	if 3 <= Y and 3 <= X:
		for i in range(3):
			for j in range(3):
				cnt += dic[(Y-i, X-j)]
		if cnt:
			ans[cnt] += 1


ans = [0]*10
for y, x in ab:
	for i in range(3):
		for j in range(3):
			if y+i <= H and x+j <= W and check[(y+i, x+j)] == 0:
				count_black(y+i, x+j)
				check[(y+i, x+j)] = 1

ans[0] = (H-2)*(W-2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    total = (H - 2) * (W - 2)
    res = [0] * 10
    used = set()
    for a, b in AB:
        if (a, b) in used:
            continue
        que = deque([(a, b)])
        while que:
            h, w = que.popleft()
            if (h, w) in used:
                continue
            used.add((h, w))
            cnt = 0
            flg = True
            tmp = []
            for dh, dw in d:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    flg = False
                else:
                    if (next_h, next_w) in AB:
                        cnt += 1
                    if (next_h, next_w) not in used:
                        tmp.append((next_h, next_w))
            if flg and cnt:
                res[cnt] += 1
            if cnt:
                for next_h, next_w in tmp:
                    que.append((next_h, next_w))
    res[0] = total - sum(res)
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    total = (H - 2) * (W - 2)
    res = [0] * 10
    used = set()
    for a, b in AB:
        if (a, b) in used:
            continue
        que = deque([(a, b)])
        while que:
            h, w = que.popleft()
            used.add((h, w))
            cnt = 0
            flg = True
            for dh, dw in d:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    flg = False
                else:
                    if (next_h, next_w) in AB:
                        cnt += 1
                    if (next_h, next_w) not in used:
                        used.add((next_h, next_w))
                        que.append((next_h, next_w))
            if flg:
                res[cnt] += 1
    t = total - sum(res)
    res[0] += t
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    total = (H - 2) * (W - 2)
    res = [0] * 10
    used = set()
    for a, b in AB:
        if (a, b) in used:
            continue
        que = deque([(a, b)])
        while que:
            h, w = que.popleft()
            if (h, w) in used:
                continue
            used.add((h, w))
            cnt = 0
            flg = True
            for dh, dw in d:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    flg = False
                else:
                    if (next_h, next_w) in AB:
                        cnt += 1
                    if (next_h, next_w) not in used:
                        que.append((next_h, next_w))
            if flg:
                res[cnt] += 1
    t = total - sum(res)
    res[0] += t
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()