Problem:


 ペンキの色  

問題

情報オリンピックの宣伝のために,長方形のベニヤ板にペンキを塗り看板を制作したい.ベニヤ板には色を塗りたくないところにあらかじめ何枚かの長方形のマスキングテープが貼られている.そこでマスキングテープで区切られた領域ごとに別々の色を使いペンキを塗ることにした.例えば,図 5-1 の場合は 5 色のペンキを使う.

入力としてマスキングテープを貼る位置が与えられた時,使うペンキの色の数を求めるプログラムを作成せよ.ただし,ベニヤ板全体がマスキングテープで覆われることはなく,全てのマスキングテープの辺はベニヤ板のいずれかの辺に平行である.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

  1 行目にはベニヤ板の幅 w (1  ≤  w  ≤  1000000 となる整数) と高さ h (1  ≤   h ≤ 1000000 となる整数) がこの順に空白区切りで書かれている.

  2 行目にはマスキングテープの数 n (1 ≤ n ≤ 1000 となる整数) が書かれている.
続く 3 行目以降の 2 + i 行目 (1 ≤ i ≤ n) には,i 番目に貼るマスキングテープの左下の座標 (x1 , y1 ) と,右上の座標 (x2 , y2 ) が x1 , y1 , x2 , y2 (0 ≤ x1 < x2 ≤  w, 0 ≤ y1 < y2 ≤  h となる整数) の順に空白区切りで書かれている.

  ただし,ベニヤ板の左下の角の座標は (0, 0) で右上の角の座標は (w, h) である.  採点用データのうち, 配点の 30% 分は w ≤ 100, h ≤ 100, n ≤ 100 を満たす.

h, w がともに 0 のとき入力の終了を示す. データセットの数は 20 を超えない．

出力

データセットごとに使うペンキの色数を１行に出力する.

入出力例

次の例は図 5-1 の場合である.

入力例

15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6
0 0

出力例

5

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6
0 0


Sample output:
5

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

def xins(x):
    if not x in xlist:
        insp = bisect.bisect(xlist,x)
        xlist.insert(insp,x)
        for lst in zaatu:
            ins = 1 if insp == 0 else lst[insp-1]
            lst.insert(insp,ins)

def yins(y):
    if not y in ylist:
        insp = bisect.bisect(ylist,y)
        ylist.insert(insp,y)
        a = [1]*(len(xlist)+1)
        if insp > 0:
            for i in range(len(xlist)):
                a[i] = zaatu[insp-1][i]
        zaatu.insert(insp,a)

def addmask(x1,y1,x2,y2):
    xins(x1)
    yins(y1)
    xins(x2)
    yins(y2)
    x1 = xlist.index(x1)
    y1 = ylist.index(y1)
    x2 = xlist.index(x2)
    y2 = ylist.index(y2)

    for i in range(y1,y2):
        for j in range(x1,x2):
            zaatu[i][j] = 0

def printcolor(zaatu,no,x,y,xlen,ylen,stack):
    if zaatu[y][x] == 1:
        zaatu[y][x] = no
        if x > 0:
            stack.append([x-1,y])
        if x < xlen:
            stack.append([x+1,y])
        if y > 0:
            stack.append([x,y-1])
        if y < ylen:
            stack.append([x,y+1])

def doprint(zaatu,no,xlen,ylen,stack):
    while len(stack) != 0:
        x,y = stack.popleft()
        printcolor(zaatu,no,x,y,xlen,ylen,stack)


while True:
    xlist = []
    ylist = []
    zaatu = [[1]]
    h,w = map(int, input().split())
    if h == 0: break
    masn = int(input())
    for i in range(masn):
        a,b,c,d = map(int,input().split())
        addmask(a,b,c,d)

    if xlist[0] != 0: xins(0)
    if ylist[0] != 0: yins(0)
    if xlist[-1] == h: xlist.pop()
    if ylist[-1] == w: ylist.pop()
    ylist.pop()


    xlen = len(xlist)
    ylen = len(ylist)
    no = 2


    for y in range(ylen):
        for x in range(xlen):
            if zaatu[y][x] == 1:
                d = deque([[x,y]])
                doprint(zaatu,no,xlen,ylen,d)
            if zaatu[y][x] == no: no += 1

    mx = 0
    for lst in zaatu:
        mx = max(mx,max(lst))
    print(mx-1)

Submission status: Wrong Answer

Solution code:
def main():
  while True:
    w, h = map(int, input().split())
    if not w:
      break
  
    n = int(input())
  
    xlst = [0, w - 1]
    ylst = [0, h - 1]
    plst = []
  
    for i in range(n):
      x1, y1, x2, y2 = map(int, input().split())
      plst.append([x1,y1,x2 - 1,y2 - 1])
      xlst.append(x1)
      xlst.append(x2)
      xlst.append(x2 - 1)
      ylst.append(y1)
      ylst.append(y2)
      ylst.append(y2 - 1)
  
    xlst = list(set(xlst))
    ylst = list(set(ylst))
    xlst.sort()
    ylst.sort()
  
    xdic = {}
    ydic = {}
  
    for i, v in enumerate(xlst):
      xdic[v] = i + 1
    for i, v in enumerate(ylst):
      ydic[v] = i + 1
    
    neww = xdic[xlst[-1]]
    newh = ydic[ylst[-1]]

    painted = [[1] * (newh + 2)]
    for _ in range(neww):
      painted.append([1] + [0] * newh +  [1])
    painted.append([1] * (newh + 2))  
  
    for p in plst:
      x1, y1, x2, y2 = p
      x1, y1, x2, y2 = xdic[x1], ydic[y1], xdic[x2], ydic[y2]
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          painted[x][y] = 1
          
    stack = []
    app = stack.append
    pp = stack.pop
    direct = ((-1, 0), (1, 0), (0, -1), (0, 1))
    ans = 0

    for x in range(1, neww + 1):
      for y in range(1, newh + 1):
        if not painted[x][y]:
          ans += 1
          painted[x][y] = 1
          app((x,y))

          while stack:
            px, py = pp()
            for dx, dy in direct:
              tx, ty = px + dx, py + dy
              if not painted[tx][ty]:
                painted[tx][ty] = 1
                app((tx,ty))
    print(ans)

main()

Submission status: Accepted

Solution code:
import queue


class XY:
    def __init__(self, x, y):
        self.x = x
        self.y = y


def compress(x1, x2, _w):
    xs = []
    for i in range(0, N):
        for d in range(-1, 2):
            tx1 = x1[i] + d
            tx2 = x2[i] + d
            if 0 <= tx1 <= _w:
                xs.append(tx1)
            if 0 <= tx2 <= _w:
                xs.append(tx2)
    xs = list(set(xs))
    xs.sort()

    for i in range(0, N):
        x1[i] = xs.index(x1[i])
        x2[i] = xs.index(x2[i])

    return len(xs) -1


if __name__ == '__main__':
    while True:
        W, H = list(map(int, input().split()))
        if W == 0 and H == 0: break
        N = int(input())
        X1 = []
        X2 = []
        Y1 = []
        Y2 = []
        for i in range(0, N):
            inputs = list(map(int, input().split()))
            X1.append(inputs[0])
            Y1.append(inputs[1])
            X2.append(inputs[2])
            Y2.append(inputs[3])

        W = compress(X1, X2, W)
        H = compress(Y1, Y2, H)
        # print(str(W) + " " + str(H))
        fld = [[False for i in range(6 * N)] for i in range(6 * N)]
        for i in range(0, N):
            for y in range(Y1[i], Y2[i]):
                for x in range(X1[i], X2[i]):
                    fld[y][x] = True
        ans = 0
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]

        # for i in range(0, 6):
        #     for j in range(0, 15):
        #         if fld[i][j]:
        #             if j != 14:
        #                 print("???", end="")
        #             else:
        #                 print("???")
        #         else:
        #             if j != 14:
        #                 print("???", end="")
        #             else:
        #                 print("???")

        for y in range(0, H):
            for x in range(0, W):
                if fld[y][x]:
                    continue
                # print("xy" + str(x) + " " + str(y))
                ans += 1

                que = []
                que.append(XY(x, y))

                while len(que) != 0:
                    xy = que.pop()
                    sx = xy.x
                    sy = xy.y
                    for i in range(0, 4):
                        tx = sx + dx[i]
                        ty = sy + dy[i]
                        if tx < 0 or W <= tx or ty < 0 or H <= ty:
                            continue
                        if fld[ty][tx]: continue
                        que.append(XY(tx, ty))
                        # print("txty" + str(tx) + " " + str(ty))
                        fld[ty][tx] = True

        print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

def xins(x):
    if not x in xlist:
        insp = bisect.bisect(xlist,x)
        xlist.insert(insp,x)
        for lst in zaatu:
            ins = 1 if insp == 0 else lst[insp-1]
            lst.insert(insp,ins)

def yins(y):
    if not y in ylist:
        insp = bisect.bisect(ylist,y)
        ylist.insert(insp,y)
        a = [1]*(len(xlist)+1)
        if insp > 0:
            for i in range(len(xlist)):
                a[i] = zaatu[insp-1][i]
        zaatu.insert(insp,a)

def addmask(x1,y1,x2,y2):
    xins(x1)
    yins(y1)
    xins(x2)
    yins(y2)
    x1 = xlist.index(x1)
    y1 = ylist.index(y1)
    x2 = xlist.index(x2)
    y2 = ylist.index(y2)

    for i in range(y1,y2):
        for j in range(x1,x2):
            zaatu[i][j] = 0

def printcolor(zaatu,no,x,y,xlen,ylen,stack):
    if zaatu[y][x] == 1:
        zaatu[y][x] = no
        if x > 0:
            stack.append([x-1,y])
        if x < xlen-1:
            stack.append([x+1,y])
        if y > 0:
            stack.append([x,y-1])
        if y < ylen-1:
            stack.append([x,y+1])

def doprint(zaatu,no,xlen,ylen,stack):
    while len(stack) != 0:
        x,y = stack.popleft()
        printcolor(zaatu,no,x,y,xlen,ylen,stack)


while True:
    xlist = []
    ylist = []
    zaatu = [[1]]
    h,w = map(int, input().split())
    if h == 0: break
    masn = int(input())
    for i in range(masn):
        a,b,c,d = map(int,input().split())
        addmask(a,b,c,d)

    if xlist[0] != 0: xins(0)
    if ylist[0] != 0: yins(0)
    if xlist[-1] == h: xlist.pop()
    if ylist[-1] == w: ylist.pop()
    zaatu.pop()
    xlen = len(xlist)
    ylen = len(ylist)
    no = 2

    for y in range(ylen):
        for x in range(xlen):
            if zaatu[y][x] == 1:
                d = deque([[x,y]])
                doprint(zaatu,no,xlen,ylen,d)
            if zaatu[y][x] == no: no += 1

    mx = 0
    for lst in zaatu:
        mx = max(mx,max(lst))
    print(mx-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000000)

while True:
  w, h = map(int, input().split())
  if not w:
    break

  n = int(input())

  xlst = [0, w - 1]
  ylst = [0, h - 1]
  plst = []

  for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    plst.append([x1,y1,x2 - 1,y2 - 1])
    xlst.append(x1)
#    xlst.append(x1 + 1)
    xlst.append(x2)
    xlst.append(x2 - 1)
    ylst.append(y1)
#    ylst.append(y1 + 1)
    ylst.append(y2)
    ylst.append(y2 - 1)

  xlst = list(set(xlst))
  ylst = list(set(ylst))
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)

  xdic = {}
  ydic = {}

  for i, v in enumerate(sorted_xlst):
    xdic[v] = i
  for i, v in enumerate(sorted_ylst):
    ydic[v] = i
  
  neww = xdic[sorted_xlst[-1]]
  newh = ydic[sorted_ylst[-1]]
#  print(neww, newh)

  painted = [[0] * (newh) for _ in range(neww)]

  def paint_area(x, y):
    painted[x][y] = 1
    for tx, ty in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
      if 0 <= tx <= neww - 1 and 0 <= ty <= newh - 1 and not painted[tx][ty]:
        paint_area(tx, ty)

  for p in plst:
    x1, y1, x2, y2 = p
    x1, y1, x2, y2 = xdic[x1], ydic[y1], xdic[x2], ydic[y2]
    for x in range(x1, x2 + 1):
      for y in range(y1, y2 + 1):
        painted[x][y] = 1
        
#  for area in painted:
#    print(area)
#  print()

  ans = 0

  for x in range(neww):
    for y in range(newh):
      if not painted[x][y]:
        ans += 1
        painted[x][y] = 1
        que = [(x, y)]
        while que:
          px, py = que.pop()
          for tx, ty in [(px - 1, py), (px + 1, py), (px, py - 1), (px, py + 1)]:
            if 0 <= tx <= neww - 1 and 0 <= ty <= newh - 1 and not painted[tx][ty]:
              painted[tx][ty] = 1
              que.append((tx,ty))
  print(ans)

Submission status: Accepted

Solution code:
def main():
  while True:
    w, h = map(int, input().split())
    if not w:
      break
  
    n = int(input())
  
    xlst = [0, w - 1]
    ylst = [0, h - 1]
    plst = []
  
    for i in range(n):
      x1, y1, x2, y2 = map(int, input().split())
      plst.append([x1,y1,x2 - 1,y2 - 1])
      xlst.append(x1)
      xlst.append(x2)
      xlst.append(x2 - 1)
      ylst.append(y1)
      ylst.append(y2)
      ylst.append(y2 - 1)
  
    xlst = list(set(xlst))
    ylst = list(set(ylst))
    sorted_xlst = sorted(xlst)
    sorted_ylst = sorted(ylst)
  
    xdic = {}
    ydic = {}
  
    for i, v in enumerate(sorted_xlst):
      xdic[v] = i
    for i, v in enumerate(sorted_ylst):
      ydic[v] = i
    
    neww = xdic[sorted_xlst[-1]]
    newh = ydic[sorted_ylst[-1]]

    painted = [[1] * (newh + 2)]
    for _ in range(neww):
      painted.append([1] + [0] * newh +  [1])
    painted.append([1] * (newh + 2))  
  
    for p in plst:
      x1, y1, x2, y2 = p
      x1, y1, x2, y2 = xdic[x1] + 1, ydic[y1] + 1, xdic[x2] + 1, ydic[y2] + 1
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          painted[x][y] = 1
          
    ans = 0
    que = []
    app = que.append
    pp = que.pop  
    for x in range(1, neww + 1):
      for y in range(1, newh + 1):
        if not painted[x][y]:
          ans += 1
          painted[x][y] = 1
          app((x,y))
          while que:
            px, py = pp()
            for tx, ty in [(px - 1, py), (px + 1, py), (px, py - 1), (px, py + 1)]:
              if not painted[tx][ty]:
                painted[tx][ty] = 1
                app((tx,ty))
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
  while True:
    w, h = map(int, input().split())
    if not w:
      break
  
    n = int(input())
  
    xlst = [0, w - 1]
    ylst = [0, h - 1]
    plst = []
  
    for i in range(n):
      x1, y1, x2, y2 = map(int, input().split())
      plst.append([x1,y1,x2 - 1,y2 - 1])
      xlst.append(x1)
      xlst.append(x2)
      xlst.append(x2 - 1)
      ylst.append(y1)
      ylst.append(y2)
      ylst.append(y2 - 1)
  
    xlst = list(set(xlst))
    ylst = list(set(ylst))
    xlst.sort()
    ylst.sort()
  
    xdic = {}
    ydic = {}
  
    for i, v in enumerate(xlst):
      xdic[v] = i
    for i, v in enumerate(ylst):
      ydic[v] = i
    
    neww = xdic[xlst[-1]]
    newh = ydic[ylst[-1]]

    painted = [[1] * (newh + 2)]
    for _ in range(neww):
      painted.append([1] + [0] * newh +  [1])
    painted.append([1] * (newh + 2))  
  
    for p in plst:
      x1, y1, x2, y2 = p
      x1, y1, x2, y2 = xdic[x1] + 1, ydic[y1] + 1, xdic[x2] + 1, ydic[y2] + 1
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          painted[x][y] = 1
    
    stack = []
    app = stack.append
    pp = stack.pop
    direct = ((-1, 0), (1, 0), (0, -1), (0, 1))
    ans = 0

    for x in range(1, neww + 1):
      for y in range(1, newh + 1):
        if not painted[x][y]:
          ans += 1
          painted[x][y] = 1
          app((x,y))

          while stack:
            px, py = pp()
            for dx, dy in direct:
              tx, ty = px + dx, py + dy
              if not painted[tx][ty]:
                painted[tx][ty] = 1
                app((tx,ty))
    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from typing import Union, List
import io, sys
import bisect
from collections import deque


def main():
    w,h = list(map(int, sys.stdin.readline().split()))
    
    if w == h == 0:
        return "END"
    
    n = int( sys.stdin.readline() )
    x1y1x2y2_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]

    X1,Y1,X2,Y2 = list(map(list, zip(*x1y1x2y2_list)))

    all_X = compress(X1,X2,w)
    all_Y = compress(Y1,Y2,h)

    matrix =[ [0]*len(all_X) for _ in range(len(all_Y)) ]
    

    for i in range(n):
        matrix[ Y1[i] ][ X1[i] ] += 1
        matrix[ Y2[i] ][ X2[i] ] += 1
        matrix[ Y2[i] ][ X1[i] ] -= 1
        matrix[ Y1[i] ][ X2[i] ] -= 1


    for row in range(len(matrix)):
        for col in range(1, len(matrix[0])):
            matrix[row][col] += matrix[row][col-1]
    
    for row in range(1, len(matrix)):
        for col in range(len(matrix[0])):
            matrix[row][col] += matrix[row-1][col]

    del matrix[-1]

    for row in range(len(matrix)):
        del matrix[row][-1]

    
    cnt = 0

    for row in range(len(matrix)):
        for col in range(len(matrix[0])):
            if matrix[row][col] == 0:
                cnt += 1
                bfs_paint(matrix, col, row, cnt)


    print(cnt)


def compress(A1 :list, A2 :list, max_A):
    all_A = []
    #delta = [-1, 0, 1]
    delta = [0]

    for a in (A1 + A2):
        for d in delta:
            val = a + d

            if 0 <= val <= max_A:
                all_A.append(a + d)

    all_A += [0, max_A]
    all_A = sorted(set(all_A))

    for i in range(len(A1)):
        A1[i] = bisect.bisect_left(all_A, A1[i])
        A2[i] = bisect.bisect_left(all_A, A2[i])
    
    return all_A


def bfs_paint(matrix :List[list], col :int, row :int, cnt :int):
    queue = deque([ (col, row) ])
    matrix[row][col] = cnt
    delta = [(0,1),(0,-1),(1,0),(-1,0)]  # (column, row)

    while queue:
        c,r = queue.popleft()

        for d in delta:
            next_c = c + d[0]
            next_r = r + d[1]

            if (0 <= next_c < len(matrix[0])) and (0 <= next_r < len(matrix)) and \
                matrix[next_r][next_c] == 0:

                matrix[next_r][next_c] = cnt
                queue.append( (next_c, next_r) )


if __name__ == "__main__":
    while True:
        ret = main()
        
        if ret == "END":
            break

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def compress(x1, x2, w):
    N = len(x1)
    xs = set()
    for i in range(N):
        for d in [0, 1]:
            tx1, tx2 = x1[i]-d, x2[i]+d
            if 0 <= tx1 < w:
                xs.add(tx1)
            if 0 <= tx2 < w:
                xs.add(tx2)
    xs = list(xs)
    xs.sort()
    for i in range(N):
        x1[i] = xs.index(x1[i])
        x2[i] = xs.index(x2[i])
    return len(xs)


while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    n = int(input())
    x1 = [0] * n
    x2 = [0] * n
    y1 = [0] * n
    y2 = [0] * n
    for i in range(n):
        x1[i], y1[i], x2[i], y2[i] = map(int, input().split())
        x2[i] -= 1
        y2[i] -= 1
    w = compress(x1, x2, w)
    h = compress(y1, y2, h)

    board = [[False] * w for _ in range(h)]
    for i in range(n):
        for y in range(y1[i], y2[i]+1):
            for x in range(x1[i], x2[i]+1):
                board[y][x] = True

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    for y in range(h):
        for x in range(w):
            if board[y][x]:
                continue
            ans += 1
            queue = deque()
            queue.append((x, y))
            while queue:
                sx, sy = queue.popleft()

                for i in range(4):
                    tx, ty = sx+dx[i], sy+dy[i]
                    if 0 <= tx < w and 0 <= ty < h and not board[ty][tx]:
                        queue.append((tx, ty))
                        board[ty][tx] = True
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def compress(A):
    """ 座標圧縮 """

    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(set(A))):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

while True:
    W, H = MAP()
    if W == H == 0:
        break
    N = INT()
    X = []
    Y = []
    XY = []
    for i in range(N):
        x1, y1, x2, y2 = MAP()
        X += [x1-1, x1, x2-1, x2]
        Y += [y1-1, y1, y2-1, y2]
        XY.append((x1, y1, x2, y2))

    # 座標圧縮
    X_zipped, _ = compress(X + [-1, 0, W])
    Y_zipped, _ = compress(Y + [-1, 0, H])
    for i in range(N):
        # 圧縮後の値に置き換え
        x1, y1, x2, y2 = XY[i]
        XY[i] = (X_zipped[x1], Y_zipped[y1], X_zipped[x2], Y_zipped[y2])

    # ここから全部圧縮後の値でやる
    H, W = len(Y_zipped), len(X_zipped)
    grid = list2d(H, W, 0)
    # 2次元いもす
    for i in range(N):
        x1, y1, x2, y2 = XY[i]
        grid[y1][x1] += 1
        grid[y2][x1] -= 1
        grid[y1][x2] -= 1
        grid[y2][x2] += 1
    for i in range(H):
        grid[i] = list(accumulate(grid[i]))
    grid = list(zip(*grid))
    for i in range(W):
        grid[i] = list(accumulate(grid[i]))
    grid = list(zip(*grid))
    # 枠を-1にしておく
    grid[0] = [-1] * W
    grid[H-1] = [-1] * W
    grid = list(zip(*grid))
    grid[0] = [-1] * H
    grid[W-1] = [-1] * H
    grid = list(zip(*grid))

    directions = ((1,0),(-1,0),(0,1),(0,-1))
    visited = list2d(H, W, 0)
    def dfs(i, j):
        if visited[i][j] or grid[i][j] != 0:
            return 0
        stack = [(i, j)]
        while stack:
            h, w = stack.pop()
            visited[h][w] = 1
            for dh, dw in directions:
                h2 = h + dh
                w2 = w + dw
                if not visited[h2][w2] and grid[h2][w2] == 0:
                    stack.append((h2, w2))
        return 1

    cnt = 0
    for i in range(1, H-1):
        for j in range(1, W-1):
            cnt += dfs(i, j)
    print(cnt)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

newboard = [[False for i in range(3000)] for j in range(3000)]
q = deque([])
def bfs(yy,xx):
    global newboard
    q.append((yy,xx))
    while len(q) > 0:
        a = q.popleft()
        newboard[a[0]][a[1]] = True
        for d in [-1,1]:
            yyy = a[0]+d
            if(yyy < newh) and (0 <= yyy):
                if(newboard[yyy][a[1]] == False):
                    q.append((yyy,a[1]))
                    newboard[yyy][a[1]] = True
        for d in [-1,1]:
            xxx = a[1]+d
            if(xxx < neww) and (0 <= xxx):
                if(newboard[a[0]][xxx] == False):
                    q.append((a[0],xxx))
                    newboard[a[0]][xxx] = True

def compress(pointx,ww): #pointx:xory座標の列を圧縮して、圧縮後のworhを返す
    newx = []
    for x in pointx:
        for i in range(2):
            xx = x+i
            if(xx < ww) : newx.append(xx)
    newxuni = list(set(newx))
    newxuni.sort()
    for i in range(len(pointx)):
        pointx[i] = bisect.bisect_left(newxuni,pointx[i])

    return len(newxuni)

while True:
    w,h = map(int ,input().split())
    
    if (w == 0) : break
    
    n = int(input())
    ptx =[0]
    pty = [0]
    for i in range(n):
        xx1,yy1,xx2,yy2 = map(int ,input().split())
        ptx.append(xx1)
        ptx.append(xx2-1)
        pty.append(yy1)
        pty.append(yy2-1)
    
    neww = compress(ptx,w)
    newh = compress(pty,h)

    
    #新しい座標で塗りつぶし(imos法？) 0のところは塗られてない
    for i in range(newh):
        for j in range(neww):
            newboard[i][j] = False 
            
    for i in range(n):
        x1,y1,x2,y2 = ptx[2*i+1],pty[2*i+1],ptx[2*i+2],pty[2*i+2]
        for j in range(x1,x2+1):
            for k in range(y1,y2+1):
                newboard[k][j] = True
    
    '''   
    for i in range(n):
        x1,y1,x2,y2 = ptx[2*i+1],pty[2*i+1],ptx[2*i+2],pty[2*i+2]
        newboard[y1][x1] += 1
        if (x2+1 < neww) and (y2+1 < newh) : newboard[y2+1][x2+1] += 1
        if (x2+1 < neww) : newboard[y1][x2+1] -= 1
        if (y2+1 < newh) : newboard[y2+1][x1] -= 1

    for i in range(newh):
        for j in range(1,neww):
            newboard[i][j] += newboard[i][j-1]
    
    for i in range(neww):
        for j in range(1,newh):
            newboard[j][i] += newboard[j-1][i] 
    '''
    #幅優先
    ans = 0
    for i in range(newh):
        for j in range(neww):
            if(newboard[i][j]) : continue
            ans += 1
            bfs(i,j)
    
    print(ans)

Submission status: Runtime Error

Solution code:
def paint(i, j, prev=0):
    global w, h, board
    board[i][j] = 0

    if i + 1 < h and board[i + 1][j]:
        paint(i + 1, j)
    if prev != 2 and j > 0 and board[i][j - 1]:
        paint(i, j - 1, 1)
    if prev != 1 and j + 1 < w and board[i][j + 1]:
        paint(i, j + 1, 2)


while True:
    w, h = map(int, input().split())
    if not w:
        break
    board = [[1] * w for _ in range(h)]

    n = int(input())
    for _ in range(n):
        x1, y1, x2, y2 = map(int, input().split())
        tape_row = [0] * (x2 - x1)
        for i in range(y1, y2):
            board[i][x1:x2] = tape_row

    counter = 0
    for i in range(h):
        for j in range(w):
            if board[i][j]:
                paint(i, j)
                counter += 1

    print(counter)

Submission status: Runtime Error

Solution code:
import bisect

def xins(x):
    if not x in xlist:
        insp = bisect.bisect(xlist,x)
        xlist.insert(insp,x)
        for lst in zaatu:
            ins = 1 if insp == 0 else lst[insp-1]
            lst.insert(insp,ins)

def yins(y):
    if not y in ylist:
        insp = bisect.bisect(ylist,y)
        ylist.insert(insp,y)
        a = [1]*(len(xlist)+1)
        if insp > 0:
            for i in range(len(ylist)):
                a[i] = zaatu[insp-1][i]
        zaatu.insert(insp,a)

def addmask(x1,y1,x2,y2):
    xins(x1)
    yins(y1)
    xins(x2)
    yins(y2)
    x1 = xlist.index(x1)
    y1 = ylist.index(y1)
    x2 = xlist.index(x2)
    y2 = ylist.index(y2)

    for i in range(y1,y2):
        for j in range(x1,x2):
            zaatu[i][j] = 0

def printcolor(zaatu,no,x,y,xlen,ylen):
    if zaatu[y][x] == 1:
        zaatu[y][x] = no
        if x > 0:
            printcolor(zaatu,no,x-1,y,xlen,ylen)
        if x < xlen:
            printcolor(zaatu,no,x+1,y,xlen,ylen)
        if y > 0:
            printcolor(zaatu,no,x,y-1,xlen,ylen)
        if y < ylen:
            printcolor(zaatu,no,x,y+1,xlen,ylen)


while True:
    xlist = []
    ylist = []
    zaatu = [[1]]
    h,w = map(int, input().split())
    if h == 0: break
    masn = int(input())
    for i in range(masn):
        a,b,c,d = map(int,input().split())
        addmask(a,b,c,d)

    if xlist[0] != 0: xins(0)
    if ylist[0] != 0: yins(0)
    if xlist[-1] == h: xlist.pop()
    if ylist[-1] == w: ylist.pop()
    ylist.pop()


    xlen = len(xlist)
    ylen = len(ylist)
    no = 2


    for y in range(ylen):
        for x in range(xlen):
            printcolor(zaatu,no,x,y,xlen,ylen)
            if zaatu[y][x] == no: no += 1

    mx = 0
    for lst in zaatu:
        mx = max(mx,max(lst))
    print(mx-1)

Submission status: Runtime Error

Solution code:
import bisect
import sys
sys.setrecursionlimit(100000)

def xins(x):
    if not x in xlist:
        insp = bisect.bisect(xlist,x)
        xlist.insert(insp,x)
        for lst in zaatu:
            ins = 1 if insp == 0 else lst[insp-1]
            lst.insert(insp,ins)

def yins(y):
    if not y in ylist:
        insp = bisect.bisect(ylist,y)
        ylist.insert(insp,y)
        a = [1]*(len(xlist)+1)
        if insp > 0:
            for i in range(len(xlist)):
                a[i] = zaatu[insp-1][i]
        zaatu.insert(insp,a)

def addmask(x1,y1,x2,y2):
    xins(x1)
    yins(y1)
    xins(x2)
    yins(y2)
    x1 = xlist.index(x1)
    y1 = ylist.index(y1)
    x2 = xlist.index(x2)
    y2 = ylist.index(y2)

    for i in range(y1,y2):
        for j in range(x1,x2):
            zaatu[i][j] = 0

def printcolor(zaatu,no,x,y,xlen,ylen):
    if zaatu[y][x] == 1:
        zaatu[y][x] = no
        if x > 0:
            printcolor(zaatu,no,x-1,y,xlen,ylen)
        if x < xlen:
            printcolor(zaatu,no,x+1,y,xlen,ylen)
        if y > 0:
            printcolor(zaatu,no,x,y-1,xlen,ylen)
        if y < ylen:
            printcolor(zaatu,no,x,y+1,xlen,ylen)


while True:
    xlist = []
    ylist = []
    zaatu = [[1]]
    h,w = map(int, input().split())
    if h == 0: break
    masn = int(input())
    for i in range(masn):
        a,b,c,d = map(int,input().split())
        addmask(a,b,c,d)

    if xlist[0] != 0: xins(0)
    if ylist[0] != 0: yins(0)
    if xlist[-1] == h: xlist.pop()
    if ylist[-1] == w: ylist.pop()
    ylist.pop()


    xlen = len(xlist)
    ylen = len(ylist)
    no = 2


    for y in range(ylen):
        for x in range(xlen):
            printcolor(zaatu,no,x,y,xlen,ylen)
            if zaatu[y][x] == no: no += 1

    mx = 0
    for lst in zaatu:
        mx = max(mx,max(lst))
    print(mx-1)

Submission status: Runtime Error

Solution code:
while True:
  w, h = map(int, input().split())
  if not w:
    break

  n = int(input())

  xlst = [0, w - 1]
  ylst = [0, h - 1]
  plst = []

  for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    plst.append([x1,y1,x2,y2])
    xlst.append(x1)
#    xlst.append(x1 + 1)
    xlst.append(x2)
#    xlst.append(x2 + 1)
    ylst.append(y1)
#    ylst.append(y1 + 1)
    ylst.append(y2)
#    ylst.append(y2 + 1)

  xlst = list(set(xlst))
  ylst = list(set(ylst))
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)

  xdic = {}
  ydic = {}

  for i, v in enumerate(xlst):
    xdic[v] = i
  for i, v in enumerate(ylst):
    ydic[v] = i

  neww = len(xlst) - 1
  newh = len(ylst) - 1

  painted = [[0] * newh for _ in range(neww)]

  def paint_area(x, y):
    painted[x][y] = 1
    to_lst = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
    for tx, ty in to_lst:
      if 0 <= tx <= neww - 1 and 0 <= ty <= newh - 1 and not painted[tx][ty]:
        paint_area(tx, ty)

  for p in plst:
    x1, y1, x2, y2 = p
    x1, y1, x2, y2 = xdic[x1], ydic[y1], xdic[x2], ydic[y2]
    for x in range(x1, x2):
      for y in range(y1, y2):
        painted[x][y] = 1

#  for area in painted:
#    print(area)

  ans = 0
  for x in range(neww):
    for y in range(newh):
      if not painted[x][y]:
        ans += 1
        paint_area(x, y)

  print(ans)