Problem:


Score: 300 points

Problem Statement

In the Ancient Kingdom of Snuke, there was a pyramid to strengthen the authority of Takahashi, the president of AtCoder Inc.

The pyramid had center coordinates (C_X, C_Y) and height H. The altitude of coordinates (X, Y) is max(H - |X - C_X| - |Y - C_Y|, 0).  

Aoki, an explorer, conducted a survey to identify the center coordinates and height of this pyramid. As a result, he obtained the following information:  

C_X, C_Y was integers between 0 and 100 (inclusive), and H was an integer not less than 1.  

Additionally, he obtained N pieces of information. The i-th of them is: "the altitude of point (x_i, y_i) is h_i."  

This was enough to identify the center coordinates and the height of the pyramid. Find these values with the clues above.  

Constraints

N is an integer between 1 and 100 (inclusive).

x_i and y_i are integers between 0 and 100 (inclusive).

h_i is an integer between 0 and 10^9 (inclusive).

The N coordinates (x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_N, y_N) are all different.

The center coordinates and the height of the pyramid can be uniquely identified.

Input

Input is given from Standard Input in the following format:  

N
x_1 y_1 h_1
x_2 y_2 h_2
x_3 y_3 h_3
:
x_N y_N h_N

Output

Print values C_X, C_Y and H representing the center coordinates and the height of the pyramid in one line, with spaces in between.  

Sample Input 1

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

Sample Output 1

2 2 6

In this case, the center coordinates and the height can be identified as (2, 2) and 6.  

Sample Input 2

2
0 0 100
1 1 98

Sample Output 2

0 0 100

In this case, the center coordinates and the height can be identified as (0, 0) and 100.

Note that C_X and C_Y are known to be integers between 0 and 100.

Sample Input 3

3
99 1 191
100 1 192
99 0 192

Sample Output 3

100 0 193

In this case, the center coordinates and the height can be identified as (100, 0) and 193.  



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


Sample output:
2 2 6

Submission status: Wrong Answer

Solution code:
n = int(input())
ha = [[-1 for _ in range(101)] for _ in range(101)]
for _ in range(n):
    xi, yi, hi = map(int, input().split())
    if hi == 0:
        ha[yi][xi] = False
        continue

    for y in range(101):
        for x in range(101):
            if not ha[y][x]:
                continue

            h = hi + abs(xi - x) + abs(yi - y)
            if ha[y][x] == -1:
                ha[y][x] = h
            elif ha[y][x] != h:
                ha[y][x] = False

for y in range(101):
    for x in range(101):
        if ha[y][x]:
            print(x, y, ha[y][x])

Submission status: Wrong Answer

Solution code:
n = int(input())
ha = [[-1 for _ in range(101)] for _ in range(101)]
for _ in range(n):
    xi, yi, hi = map(int, input().split())
    if hi == 0:
        continue

    for y in range(101):
        for x in range(101):
            if not ha[y][x]:
                continue

            h = hi + abs(xi - x) + abs(yi - y)
            if ha[y][x] == -1:
                ha[y][x] = h
            elif ha[y][x] != h:
                ha[y][x] = False

for y in range(101):
    for x in range(101):
        if ha[y][x]:
            print(x, y, ha[y][x])

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    check = True
    for test in IN[1:]:
      calc_h = max([temp_h - abs(test[0]-i) - abs(test[1]-j), 0])
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)
      exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    if temp_h <= 0:
      continue
    check = True
    for test in IN[1:]:
      calc_h = max([temp_h - abs(test[0]-i) - abs(test[1]-j), 0])
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)
      exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    if temp_h <= 0:
      continue
    check = True
    for test in IN[1:]:
      calc_h = max([temp_h - abs(test[0]-i) - abs(test[1]-j), 0])
      if calc_h != test[2]:
        check = False
        break
    if check and N != 1:
      print(i, j, temp_h)

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    if temp_h <= 0:
      continue
    check = True
    for test in IN[1:]:
      calc_h = max([temp_h - abs(test[0]-i) - abs(test[1]-j), 0])
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]
 
for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    if temp_h < 0:
      continue
    check = True
    for test in IN[1:]:
      calc_h = max([temp_h - abs(test[0]-i) - abs(test[1]-j), 0])
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    check = True
    for test in IN[1:]:
      calc_h = temp_h - abs(test[0]-i) - abs(test[1]-j)
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)

Submission status: Wrong Answer

Solution code:
N = int(input())
IN = [list(map(int, input().split())) for i in range(N)]

for i in range(10):
  for j in range(10):
    test = IN[0]
    temp_h = abs(test[0]-i) + abs(test[1]-j) + test[2]
    check = True
    for test in IN[1:]:
      calc_h = temp_h - abs(test[0]-i) - abs(test[1]-j)
      if calc_h != test[2]:
        check = False
        break
    if check:
      print(i, j, temp_h)

Submission status: Wrong Answer

Solution code:
import itertools as its

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

for x, y in its.product(range(101), range(101)):
    h_list = list(set([ph + abs(x-px) + abs(y-py) for px, py, ph in P]))
    if len(h_list) == 1 and h_list[0] >= 1:
        print(x, y, h_list[0])
        exit()

Submission status: Wrong Answer

Solution code:
import itertools as its

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

for x, y in its.product(range(101), range(101)):
    h_set = set([ph + abs(x-px) + abs(y-py) for px, py, ph in P])
    if len(h_set) == 1:
        print(x, y, list(h_set)[0])

Submission status: Wrong Answer

Solution code:
import itertools as its

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

for p in P:
    if p[2] == 100:
        print(*p)
        exit()

for x, y in its.product(range(101), range(101)):
    h_set = set([ph + abs(x-px) + abs(y-py) for px, py, ph in P])
    if len(h_set) == 1:
        print(x, y, list(h_set)[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

for p in P:
    if p[2] == 100:
        print(*p)
        exit()

Submission status: Wrong Answer

Solution code:
N = int(input())

x = []
y = []
h = []


for i in range(N) : 
    a, b, c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)


for px in range(101) : 
    for py in range(101) : 

        flag = 1
        H = h[0] + abs(x[0] -px) + abs(y[0] -py)
    
        for i in range(1, N, 1) : 
            if h[i] == 0 : 
                flag = 0
                break
            elif H != h[i] + abs(x[i] -px) + abs(y[i] -py) : 
                flag = 0
                break
            
        if flag == 1 : 
            print(px, py, H)

Submission status: Wrong Answer

Solution code:
N = int(input())

x = []
y = []
h = []


for i in range(N) : 
    a, b, c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)


for px in range(101) : 
    for py in range(101) : 

        flag = 1
        H = h[0] + abs(x[0] -px) + abs(y[0] -py)
    
        for i in range(1, N, 1) : 
            if H != h[i] + abs(x[i] -px) + abs(y[i] -py) : 
                flag = 0
                break
            
        if flag == 1 : 
            print(px, py, H)

Submission status: Wrong Answer

Solution code:
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    if xyh[i][2]>0:
        tx,ty,th=xyh.pop(i)
        break
for cx in range(101):
    for cy in range(101):
        H=th+abs(tx-cx)+abs(ty-cy)
        for x,y,h in xyh:
            if H!=h+abs(x-cx)+abs(y-cy) or (h==0 and max(0,H-abs(x-cx)-abs(y-cy))!=0):
                break
        else:
            print(cx,cy,H)
            exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    if xyh[i][2]>0:
        tx,ty,th=xyh.pop(i)
        break
for cx in range(101):
    for cy in range(101):
        H=th+abs(tx-cx)+abs(ty-cy)
        for x,y,h in xyh:
            if H!=h+abs(x-cx)+abs(y-cy):
                break
        else:
            print(cx,cy,H)
            exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
xyh=[[x,y,h] for x,y,h in [list(map(int,input().split())) for i in range(n)] if h!=0]
for cx in range(101):
    for cy in range(101):
        H=0
        for x,y,h in xyh:
            if H==0:H=h+abs(x-cx)+abs(y-cy)
            elif H!=h+abs(x-cx)+abs(y-cy):
                break
        else:
            print(cx,cy,H)
            exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]

for cx in range(101):
    for cy in range(101):
        H=-1
        for x,y,h in xyh:
            if h==0:break
            elif H<0:H=h+abs(x-cx)+abs(y-cy)
            elif H!=h+abs(x-cx)+abs(y-cy):
                break
        else:
            print(cx,cy,H)
            exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
x,y,h = [],[],[]
idx = 0
for i in range(n):
    a,b,c = map(int,input().split())
    x.append(a)
    y.append(b)
    h.append(c)
    if c != 0:
        idx = i

for cx in range(101):
    for cy in range(101):
        # h[i] = H - abs(x[i]-cx) - abs(y[i]-cy)
        H = h[i] + abs(x[i]-cx) + abs(y[i]-cy)

        ok = True
        for i in range(n):
            if h[i] != max(H - abs(x[i]-cx) - abs(y[i]-cy), 0):
                ok = False
        if ok:
            print(cx,cy,H)

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
x, y, h = [inf[i] for i in range(n) if inf[i][2] > 0][0]
for cx in range(100, -1, -1):
    for cy in range(100, -1, -1):
        H = h + abs(cx - x) + abs(cy - y)
        if H < 1:
            continue
        for x1, y1, h1 in inf:
            if h1 == 0:
                continue
            H1 = h1 + abs(cx - x1) + abs(cy - y1)
            if H1 != H:
                break
        else:
            print(cx, cy, H, sep=' ')
            exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
inf = [inf[i] for i in range(n) if inf[i][2] > 0]
x, y, h = inf[0]
for cx in range(100, -1, -1):
    for cy in range(100, -1, -1):
        H = h + abs(cx - x) + abs(cy - y)
        if H < 1:
            continue
        for x1, y1, h1 in inf:
            H1 = h1 + abs(cx - x1) + abs(cy - y1)
            if H1 != H:
                break
        else:
            print(cx, cy, H, sep=' ')
            exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
x, y, h = [inf[i] for i in range(n) if inf[i][2] > 0][0]
for cx in range(100, -1, -1):
    for cy in range(100, -1, -1):
        H = h + abs(cx - x) + abs(cy - y)
        if H < 1:
            continue
        for x1, y1, h1 in inf:
            H1 = h1 + abs(cx - x1) + abs(cy - y1)
            if H1 != H:
                break
        else:
            print(cx, cy, H, sep=' ')
            exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
x, y, h = [inf[i] for i in range(n) if inf[i][2] > 0][0]
for cx in range(101):
    for cy in range(101):
        H = h + abs(cx - x) + abs(cy - y)
        if H < 1:
            continue
        for x1, y1, h1 in inf:
            H1 = h1 + abs(cx - x1) + abs(cy - y1)
            if H1 != H:
                break
        else:
            print(cx, cy, H, sep=' ')
            exit()

Submission status: Wrong Answer

Solution code:
N = int(input())

lst = []
for i in range(N):
    a = list(map(int, input().split()))
    lst += [a]

#print (lst)

#中心座標(px, py)
for px in range(101):
    for py in range(101):
#        print ('px, py ', px, py)
        j = 0
        while lst[j][2] == 0:
            j += 1
        h = lst[j][2] + abs(px-lst[j][0]) + abs(py -lst[j][1])
#        print ('j, h ', j, h)
        k = 0
        while k < N:
            if lst[k][2] == max(h - abs(px-lst[k][0]) - abs(py -lst[k][1]), 0):
                k += 1
#                print ('A')
            else:
#                print ('B')
                k = 100
        if k == N:
            print (px, py, h)
        else:
            pass
#            print ('C')

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
candidate  = []
x1, y1, h1 = [inf[i] for i in range(n) if inf[i][2] > 0][0]
for i in range(n):
    x2, y2, h2 = inf[i]
    for cx in range(101):
        for cy in range(101):
            if h1 - h2 == abs(cx - x2) - abs(cx - x1) \
                        + abs(cy - y2) - abs(cy - y1):
                          candidate.append([cx, cy])
for cx, cy in candidate:
    H0 = inf[0][2] + abs(cx - inf[0][0]) + abs(cy - inf[0][1])
    for x, y, h in inf:
        H = h + abs(cx - x) + abs(cy - y)
        if not H == H0:
            break
    else:
        print(cx, cy, H0, sep=' ')
        exit()

Submission status: Wrong Answer

Solution code:
N = int(input())

lst = []
for i in range(N):
    a = list(map(int, input().split()))
    lst += [a]

#print (lst)

#中心座標(px, py)
for px in range(101):
    for py in range(101):
#        print ('px, py ', px, py)
        j = 0
        while lst[j][2] == 0:
            j += 1
        h = lst[j][2] + abs(px-lst[j][0]) + abs(py -lst[j][1])
#        print ('j, h ', j, h)
        k = 0
        while k < N:
            if lst[k][2] == h - abs(px-lst[k][0]) - abs(py -lst[k][1]):
                k += 1
#                print ('A')
            else:
#                print ('B')
                k = 100
        if k == N:
            print (px, py, h)
        else:
            pass
#            print ('C')

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
candidate  = []
for i in range(n):
    for j in range(n):
        x1, y1, h1 = inf[i]
        x2, y2, h2 = inf[j]
        for cx in range(max(x1, x2), 101):
            for cy in range(max(y1, y2), 101):
                if h1 - h2 == abs(cx - x2) - abs(cx - x1) \
                            + abs(cy - y2) - abs(cy - y1):
                              candidate.append([cx, cy])
for cx, cy in candidate:
    H0 = inf[0][2] + abs(cx - inf[0][0]) + abs(cy - inf[0][1])
    for x, y, h in inf:
        H = h + abs(cx - x) + abs(cy - y)
        if not H == H0:
            break
    else:
        print(cx, cy, H0, sep=' ')
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = [list(map(int, input().split())) for i in range(n)]
candidate  = []
for i in range(n):
    x1, y1, h1 = inf[0]
    x2, y2, h2 = inf[i]
    for cx in range(101):
        for cy in range(101):
            if h1 - h2 == abs(cx - x2) - abs(cx - x1) \
                        + abs(cy - y2) - abs(cy - y1):
                          candidate.append([cx, cy])
for cx, cy in candidate:
    H0 = inf[0][2] + abs(cx - inf[0][0]) + abs(cy - inf[0][1])
    for x, y, h in inf:
        H = h + abs(cx - x) + abs(cy - y)
        if not H == H0:
            break
    else:
        print(cx, cy, H0, sep=' ')
        exit()

Submission status: Wrong Answer

Solution code:
import collections
#入力
N = int(input())

dp = [[None]* 101 for _ in range(101)] #101×101の盤面
check = [[None]* 101 for _ in range(101)] #101×101の盤面　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if check[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if check[nx][ny] == None: #checkが入っていないとき
                            check[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if dp[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        dp[x][y] = h
    elif dp2[x][y] != check[x][y]:
        dp[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if dp[nx][ny] == None: #checkが入っていないとき
                            dp[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == dp[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                dp[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

if ans_x == -1 and ans_y == -1:
    for h in range(N):
        a, b, c = lst[h]
        bfs2(a,b,c)
    for i in range(101):
        for j in range(101):
            if ans < dp[i][j]:
                ans = max(ans, dp[i][j])
                ans_x, ans_y = i, j



print (ans_x, ans_y, ans)
#print (check)

Submission status: Wrong Answer

Solution code:
import collections
#入力
N = int(input())

dp = [[None]* 101 for _ in range(101)] #101×101の盤面
check = [[None]* 101 for _ in range(101)] #101×101の盤面　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if check[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if check[nx][ny] == None: #checkが入っていないとき
                            check[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if dp[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        dp[x][y] = h
    elif dp2[x][y] != check[x][y]:
        dp[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if dp[nx][ny] == None: #checkが入っていないとき
                            dp[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == dp[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                dp[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

if ans_x == -1 and ans_y == -1:
    for h in range(N):
        a, b, c = lst[h]
        bfs2(a,b,c)
    for i in range(101):
        for j in range(101):
            if ans < dp[i][j]:
                ans = max(ans, check[i][j])
                ans_x, ans_y = i, j



print (ans_x, ans_y, ans)
#print (check)

Submission status: Wrong Answer

Solution code:
import collections
#入力
N = int(input())

dp = [[None]* 101 for _ in range(101)] #101×101の盤面
check = [[None]* 101 for _ in range(101)] #101×101の盤面　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if check[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if check[nx][ny] == None: #checkが入っていないとき
                            check[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] #101×101の盤面　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h #bfsのスタート地点を記入
    if check[x][y] == None: #重ね合わせた結果が入っていない場合、記録する
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    #print ('check', check)
    q = collections.deque()
    q.append([x, y]) #スタート地点をqueueに記録
    #print (q)
    while True: #常にループ
        #print ('True') 
        if not q: #dequeが空になっていたら終わる
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: #deque内に要素が入っているとき
            px, py = q.popleft() #要素を1組取り出す
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: #範囲内の確認
                    if dp2[nx][ny] == -1: #初めて訪れる時
                        if check[nx][ny] == None: #checkが入っていないとき
                            check[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            dp2[nx][ny] = dp2[px][py] + 1 #移動前のマス+1が移動先の値
                            q.append([nx, ny]) #移動先の地点を表す組をdequeに記録
                            #print (check)
                            #print ('C')
                        else: #checkが入っているとき
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: #今回求めたdp2と記録されているcheckが等しい時
                                #print ('(nx, ny)', nx, ny)
                                pass
                            else: #一致しない時
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

print (ans_x, ans_y, ans)
#print (check)