Problem:


コンビニ

 コンビニエンスストア・デブンイレブンは事業を広げるため若松市に一店舗目をオープンしようと考えています。若松市には既に他のたくさんのコンビニエンスストアがあるので、新店舗をオープンする場所が成功の鍵を握ることになりそうです。デブンイレブンは「お客さんは自分の住んでいる地域から最も近いコンビニを利用する」という前提の下、「多くのお客さんが利用するであろう地点」に出店することにしています。

デブンイレブンは、既設の各コンビニがカバーしている範囲を把握するため、若松市の地図を合同な正六角形(以後「ブロック」)を用いて区分しました。このとき、各ブロックには既設のコンビニが多くとも一つだけ入るように区分しました。この地図上で、各ブロックからあるコンビニへ行くのに経由するブロックの数をもとにコンビニとの距離を求めます。各ブロックはこの距離が最も小さいコンビニによってカバーされていると考えます。問題は、この地図をもとに「できるだけ多くのブロックをカバーする既設のコンビニがないブロック」を探すことです。

 デブンイレブンのプログラマであるあなたは、ブロック分けされた地図情報と新店舗の候補地の情報から、最も広くカバーできるブロック数を計算するプログラムを開発することになりました。
 

 

 m &times; n に区分した地図は図1のように表します。六角形のブロックが横に m 個、縦に n 個並び、それぞれは一つの座標(x, y)で示されます。奇数行の左端はその上の行の左端の左下に、偶数行の左端はその上の行の左端の右下に、それぞれ位置します。例えば、座標(1, 1)は図1の一番左上のブロックを示します。また、座標(1, 2)は座標(1, 1)の右下に位置し、座標(1, 3)は座標(1, 2)の左下に位置します。

 図2は既設のコンビニが6個あった場合の例で、6 &times; 6 に区分されています。各コンビニは1から順に番号が振られています。このとき、各コンビニがカバーするブロックを番号毎に塗り分けると図3のようになります。座標(1, 4)や(2, 5)のように塗られていないブロックは最も近いコンビニが二つ以上あり、どちらとも判断がつかないブロックになっています。例えば、座標(1, 4)のブロックの場合、番号4のコンビニと番号5のコンビニへの距離が等しく、このブロックをカバーしているコンビニはないものとして考えます。番号4のコンビニがカバーしているブロック数は5となります。

 ここで、デブンイレブンが座標(1, 3)と座標(5, 3)を新店舗の候補地として考えているとします。座標(1, 3)に店舗を構えた場合、カバーできるブロック数は3となります(図4)。一方、座標(5, 3)に店舗を構えた場合にカバーできるブロック数は4となります(図5)。したがって、最も広くカバーできるブロック数は4となります。

 地図情報 m &times; n、既設のコンビニの数 s とその座標(x, y)、候補地の数 t とその座標(p, q)を入力とし、全候補地の中で最も広くカバーできるブロック数を出力するプログラムを作成してください。

Input

 複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下の形式で与えられます。

m n
s
x1 y1
x2 y2
:
xs ys
t
p1 q1
p2 q2
:
pt qt

 1 行目に区分した地図の大きさ(横、縦)を表す整数 m, n (2 ≤ m, n ≤ 100) が与えられます。

2行目に既設のコンビニの数 s (1 ≤ s ≤ 10) が与えられます。続くs 行に、 i 個目の既設のコンビニの座標 xi, y1  が与えられます。

続く行に、新店舗の候補地の数 t (1 ≤ t ≤ 10 ) が与えられます。続く t 行に、i 個目の候補地の座標 pi, qi が与えられます。

データセットの数は 20 を超えません。

Output

データセット毎に、全候補地の中で最も広くカバーできるブロック数を１行に出力します。

Sample Input

6 6
6  
1 1
6 1
3 2
3 5
1 6
5 6
2
1 3
5 3
6 6
6
3 2
3 5
6 1
1 1
1 6
5 6
2
2 3
5 3
0 0

Output for the Sample Input

4
4



Sample input:
6 6
6
1 1
6 1
3 2
3 5
1 6
5 6
2
1 3
5 3
6 6
6
3 2
3 5
6 1
1 1
1 6
5 6
2
2 3
5 3
0 0


Sample output:
4
4

Submission status: Accepted

Solution code:
import sys

def generate_next_hexes(x, y):
    hexes = list()
    hexes.append((x, y - 1))
    hexes.append((x, y + 1))
    hexes.append((x - 1, y))
    hexes.append((x + 1, y))
    if y % 2:
        hexes.append((x - 1, y - 1))
        hexes.append((x - 1, y + 1))
    else:
        hexes.append((x + 1, y - 1))
        hexes.append((x + 1, y + 1))
    return hexes

def update_map(hex_map, hexes):
    num_updated_hexes = 0
    distance = 0
    while hexes:
        next_hexes = []
        for pos in hexes:
            x = pos[0]
            y = pos[1]
            if (1 <= x <= m and 1 <= y <= n
                    and (pos not in hex_map or distance < hex_map[pos])):
                hex_map[pos] = distance
                num_updated_hexes += 1
                next_hexes += generate_next_hexes(x, y)
        distance += 1
        hexes = next_hexes
    return num_updated_hexes

while True:
    (m, n) = [int(i) for i in sys.stdin.readline().split()]
    if m == n == 0:
        break

    s = int(sys.stdin.readline())
    stores = []
    for i in range(s):
        cord = [int(j) for j in sys.stdin.readline().split()]
        stores.append(tuple(cord))
    hex_map = {}
    update_map(hex_map, stores)

    t = int(sys.stdin.readline())
    candidates = []
    for i in range(t):
        cord = [int(j) for j in sys.stdin.readline().split()]
        candidates.append(tuple(cord))

    # search max num
    max_num_blocks = 0
    for candidate in candidates:
        new_hex_map = hex_map.copy()
        num_blocks = update_map(new_hex_map, [candidate])
        max_num_blocks = max(max_num_blocks, num_blocks)

    print(max_num_blocks)

Submission status: Accepted

Solution code:
import sys

def generate_next_hexes(x, y):
    hexes = [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]
    if y % 2:
        hexes += [(x - 1, y - 1), (x - 1, y + 1)]
    else:
        hexes += [(x + 1, y - 1), (x + 1, y + 1)]
    return hexes

def update_map(hex_map, hexes):
    num_updated_hexes = 0
    distance = 0
    while hexes:
        next_hexes = []
        for pos in hexes:
            if (1 <= pos[0] <= m and 1 <= pos[1] <= n) and (pos not in hex_map or distance < hex_map[pos]):
                hex_map[pos] = distance
                num_updated_hexes += 1
                next_hexes += generate_next_hexes(pos[0], pos[1])
        distance += 1
        hexes = next_hexes
    return num_updated_hexes

while True:
    (m, n) = [int(i) for i in sys.stdin.readline().split()]
    if m == n == 0:
        break

    s = int(sys.stdin.readline())
    stores = []
    for i in range(s):
        pos = [int(j) for j in sys.stdin.readline().split()]
        stores.append(tuple(pos))
    hex_map = {}
    update_map(hex_map, stores)

    t = int(sys.stdin.readline())
    candidates = []
    for i in range(t):
        pos = [int(j) for j in sys.stdin.readline().split()]
        candidates.append(tuple(pos))

    max_num_blocks = 0
    for candidate in candidates:
        new_hex_map = hex_map.copy()
        num_blocks = update_map(new_hex_map, [candidate])
        max_num_blocks = max(max_num_blocks, num_blocks)

    print(max_num_blocks)

Submission status: Accepted

Solution code:
import sys

def generate_next_hexes(x, y):
    hexes = [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]
    if y % 2:
        hexes += [(x - 1, y - 1), (x - 1, y + 1)]
    else:
        hexes += [(x + 1, y - 1), (x + 1, y + 1)]
    return hexes

def update_map(hex_map, hexes):
    num_updated_hexes = 0
    distance = 0
    while hexes:
        next_hexes = []
        for pos in hexes:
            x = pos[0]
            y = pos[1]
            if (1 <= x <= m and 1 <= y <= n
                    and (pos not in hex_map or distance < hex_map[pos])):
                hex_map[pos] = distance
                num_updated_hexes += 1
                next_hexes += generate_next_hexes(x, y)
        distance += 1
        hexes = next_hexes
    return num_updated_hexes

while True:
    (m, n) = [int(i) for i in sys.stdin.readline().split()]
    if m == n == 0:
        break

    s = int(sys.stdin.readline())
    stores = []
    for i in range(s):
        pos = [int(j) for j in sys.stdin.readline().split()]
        stores.append(tuple(pos))
    hex_map = {}
    update_map(hex_map, stores)

    t = int(sys.stdin.readline())
    candidates = []
    for i in range(t):
        pos = [int(j) for j in sys.stdin.readline().split()]
        candidates.append(tuple(pos))

    max_num_blocks = 0
    for candidate in candidates:
        new_hex_map = hex_map.copy()
        num_blocks = update_map(new_hex_map, [candidate])
        max_num_blocks = max(max_num_blocks, num_blocks)

    print(max_num_blocks)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10 ** 5
direct1 = ((-1, 0), (1, 0), (0, -1), (0, 1), (1, -1), (1, 1))
direct2 = ((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0))

def search(p, mp):
  que = deque()
  que.append((0, p))
  visited = [[False] * (m + 2) for _ in range(n + 2)]
  visited[p[1]][p[0]] = True
  mp[p[1]][p[0]] = 0
  while que:
    dist, point = que.popleft()
    px, py = point
    if py % 2 == 0:
      direct = direct1
    else:
      direct = direct2
    for dx, dy in direct:
      nx, ny = px + dx, py + dy
      if not visited[ny][nx] and mp[ny][nx] != -1:
        visited[ny][nx] = True
        if mp[ny][nx] > dist + 1:
          mp[ny][nx] = dist + 1
        que.append((dist + 1, (nx, ny)))

def count(p, mp):
  que = deque()
  que.append((0, p))
  visited = [[False] * (m + 2) for _ in range(n + 2)]
  visited[p[1]][p[0]] = True
  ans = 1
  while que:
    dist, point = que.popleft()
    px, py = point
    if py % 2 == 0:
      direct = direct1
    else:
      direct = direct2
    for dx, dy in direct:
      nx, ny = px + dx, py + dy
      if not visited[ny][nx] and mp[ny][nx] != -1:
        visited[ny][nx] = True
        if mp[ny][nx] > dist + 1:
          ans += 1
        que.append((dist + 1, (nx, ny)))
  return ans


while True:
  m, n = map(int, input().split())
  if m == 0:
    break

  mp = [[-1] + [INF] * m + [-1] for _ in range(n)] 
  mp.insert(0, [-1] * (m + 2))
  mp.append([-1] * (m + 2))
  
  s = int(input())
  for _ in range(s):
    x, y = map(int, input().split())
    search((x, y), mp)
  
  ans = 0
  t = int(input())
  for _ in range(t):
    x, y = map(int, input().split())
    z = count((x, y), mp)
    ans = max(ans, z)
  
  print(ans)

Submission status: Accepted

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    try:
        data = raw_input()
        if data == "0":
            break
        m, n = map(int, data.split())
        s = input()
        spos = [map(int, raw_input().split()) for _ in xrange(s)]
        t = input()
        tpos = [map(int, raw_input().split()) for _ in xrange(t)]
        print solve()
    except:
        break

Submission status: Accepted

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    m, n = map(int, data.split())
    if m == 0:
        break
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Accepted

Solution code:
from collections import deque
dd0 = ((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0))
dd1 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0))

def solve(S, p, q):
    INF = 10**9
    L = [[0]*M for i in range(N)]
    D = [[INF]*M for i in range(N)]
    que = deque()
    for i, (x, y) in enumerate(S):
        L[y][x] = 1
        D[y][x] = 0
        que.append((x, y))
    L[q][p] = 2
    D[q][p] = 0
    que.append((p, q))
    while que:
        x, y = que.popleft()
        l = L[y][x]
        d0 = D[y][x] + 1
        for dx, dy in (dd1 if y % 2 else dd0):
            nx = x + dx; ny = y + dy
            if not 0 <= nx < M or not 0 <= ny < N or D[ny][nx] < d0:
                continue
            d = D[ny][nx]
            if d == INF:
                D[ny][nx] = d0
                que.append((nx, ny))
            L[ny][nx] |= l
    res = 0
    for i in range(N):
        for j in range(M):
            if L[i][j] == 2:
                res += 1
    return res

while 1:
    M, N = map(int, input().split())
    if M == N == 0:
        break
    s = int(input())
    S = []
    for i in range(s):
        x, y = map(int, input().split())
        S.append((x-1, y-1))
    t = int(input())
    ans = 0
    for i in range(t):
        p, q = map(int, input().split())
        ans = max(ans, solve(S, p-1, q-1))
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

def generate_next_hexes(x, y):
    hexes = [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]
    if y % 2:
        hexes += [(x - 1, y - 1), (x - 1, y + 1)]
    else:
        hexes += [(x + 1, y - 1), (x + 1, y + 1)]
    hexes = [(a, b) for (a, b) in hexes if 1 <= b <= m and 1 <= b <= n]
    return hexes

def update_map(hex_map, hexes):
    num_updated_hexes = 0
    distance = 0
    while hexes:
        next_hexes = []
        for pos in hexes:
            if pos not in hex_map or distance < hex_map[pos]):
                hex_map[pos] = distance
                num_updated_hexes += 1
                next_hexes += generate_next_hexes(pos[0], pos[1])
        distance += 1
        hexes = next_hexes
    return num_updated_hexes

while True:
    (m, n) = [int(i) for i in sys.stdin.readline().split()]
    if m == n == 0:
        break

    s = int(sys.stdin.readline())
    stores = []
    for i in range(s):
        pos = [int(j) for j in sys.stdin.readline().split()]
        stores.append(tuple(pos))
    hex_map = {}
    update_map(hex_map, stores)

    t = int(sys.stdin.readline())
    candidates = []
    for i in range(t):
        pos = [int(j) for j in sys.stdin.readline().split()]
        candidates.append(tuple(pos))

    max_num_blocks = 0
    for candidate in candidates:
        new_hex_map = hex_map.copy()
        num_blocks = update_map(new_hex_map, [candidate])
        max_num_blocks = max(max_num_blocks, num_blocks)

    print(max_num_blocks)

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:            
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover

def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]    
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min(sc[y][x] for sc in scover):
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:            
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m and cover[ny][nx] < 0:
                q.append((ny, nx, step + 1))
    return cover

def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min(sc[y][x] for sc in scover):
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)), ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:            
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m and cover[ny][nx] < 0:
                q.append((ny, nx, step + 1))
    return cover

def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min(sc[y][x] for sc in scover):
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dy, dx in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]   
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min(sc[y][x] for sc in scover):
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0 and len(q) <= (10 ** 5):
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0 and len(q) <= (10 ** 3):
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    return cover
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    return cover
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        return ret
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    return cover
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover

def count(cover, min_cover):
    ret = 0
    return ret
    for y in xrange(n):
        for x in xrange(m):
            if cover[y][x] < min_cover[y][x]:
                ret += 1
    return ret
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    return max(count(func(pos[1] - 1, pos[0] - 1), min_cover) for pos in tpos)
 
while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    data = raw_input().strip()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
import re
p = re.compile("\d+\s\d+")
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    if p.match(data) is None:
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
import re
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input().sprit()
    if data == "0 0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

Submission status: Runtime Error

Solution code:
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input().sprit()
    m, n = map(int, data.split())
    if m | n == 0:
        break
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()