Problem:

Estimating the Flood Risk

  Mr. Boat is the owner of a vast extent of land. As many typhoons have struck Japan this year, he became concerned of flood risk of his estate and he wants to know the average altitude of his land. The land is too vast to measure the altitude at many spots. As no steep slopes are in the estate, he thought that it would be enough to measure the altitudes at only a limited number of sites and then approximate the altitudes of the rest based on them.

  Multiple approximations might be possible based on the same measurement results, in which case he wants to know the worst case, that is, one giving the lowest average altitude.

  Mr. Boat’s estate, which has a rectangular shape, is divided into grid-aligned rectangular areas of the same size. Altitude measurements have been carried out in some of these areas, and the measurement results are now at hand. The altitudes of the remaining areas are to be approximated on the assumption that altitudes of two adjoining areas sharing an edge differ at most 1.

  In the first sample given below, the land is divided into 5 &times; 4 areas. The altitudes of the areas at (1, 1) and (5, 4) are measured 10 and 3, respectively. In this case, the altitudes of all the areas are uniquely determined on the assumption that altitudes of adjoining areas differ at most 1.

  In the second sample, there are multiple possibilities, among which one that gives the lowest average altitude should be considered.

In the third sample, no altitude assignments satisfy the assumption on altitude differences.

  Your job is to write a program that approximates the average altitude of his estate. To be precise, the program should compute the total of approximated and measured altitudes of all the mesh-divided areas. If two or more different approximations are possible, the program should compute the total with the severest approximation, that is, one giving the lowest total of the altitudes.

Input

  The input consists of a single test case of the following format.

$w$ $d$ $n$
$x_1$ $y_1$ $z_1$
.
.
.
$x_n$ $y_n$ $z_n$

Here, $w$, $d$, and $n$ are integers between $1$ and $50$, inclusive. $w$ and $d$ are the numbers of areas in the two sides of the land. $n$ is the number of areas where altitudes are measured. The $i$-th line of the following $n$ lines contains three integers, $x_i$, $y_i$, and $z_i$ satisfying $1 \leq x_i \leq w$, $1 \leq y_i \leq d$, and $−100 \leq  z_i \leq 100$. They mean that the altitude of the area at $(x_i
, y_i)$ was measured to be $z_i$. At most one measurement result is given for the same area, i.e., for $i \ne j$, $(x_i, y_i) \ne (x_j , y_j)$.

Output

  If all the unmeasured areas can be assigned their altitudes without any conflicts with the measured altitudes assuming that two adjoining areas have the altitude difference of at most 1, output an integer that is the total of the measured or approximated altitudes of all the areas. If more than one such altitude assignment is possible, output the minimum altitude total among the possible assignments.

  If no altitude assignments satisfy the altitude difference assumption, output No.

Sample Input 1 

5 4 2
1 1 10
5 4 3

Sample Output 1

130

Sample Input 2 

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

Sample Output 2

-14

Sample Input 3 

3 3 2
1 1 8
3 3 3

Sample Output 3

No

Sample Input 4 

2 2 1
1 1 -100

Sample Output 4

-404



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


Sample output:
130

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import math
import bisect
import queue

w, d, n = map(int, input().strip().split())

mapper = [[-1000 for i in range(55)] for j in range(55)]
step = [[0, 1], [0, -1], [1, 0], [-1, 0]]

arr = []

for i in range(n):
    tmp = tuple(map(int, stdin.readline().strip().split()))
    arr.append(tmp)

flag = 1

for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1]) < abs(arr[i][2] - arr[j][2]):
            flag = 0
            break
    if flag == 0:
        break

if flag == 0:
    stdout.writelines('No\n')
else:
    for each in arr:
        mapper[each[0]][each[1]] = each[2]
        chk = [[0 for i in range(55)] for j in range(55)]
        chk[each[0]][each[1]] = 1
        pend = queue.Queue()
        pend.put(each)
        while pend.qsize():
            top = pend.get()
            for each in step:
                newpos = [top[0] - each[0], top[1] - each[1]]
                if newpos[0] > 0 and newpos[0] <= w and newpos[1] > 0 and newpos[1] <= d and chk[newpos[0]][newpos[1]] < 1:
                    mapper[newpos[0]][newpos[1]] = max(mapper[newpos[0]][newpos[1]], top[2] - 1)
                    chk[newpos[0]][newpos[1]] += 1
                    pend.put((newpos[0], newpos[1], mapper[newpos[0]][newpos[1]]))
    ans = 0
    for i in range(1, w + 1):
        for j in range(1, d + 1):
            ans += mapper[i][j]
    stdout.writelines(str(ans) + '\n')

Submission status: Accepted

Solution code:
def isValid(row, col, ROWS, COLS):
    return row >= 0 and row < ROWS and col >= 0 and col < COLS

def isSteep(board, row, col, ROWS, COLS):
    global adjR, adjC

    h = board[row][col]
    for i in range(4):
        rr = row + adjR[i]
        cc = col + adjC[i]
        if isValid(rr, cc, ROWS, COLS):
            diff = abs(h - board[rr][cc])
            if diff > 1:
                return True
    return False

def update(board, row, col, ROWS, COLS):
    global adjR, adjC, given
    arr = []

    h = board[row][col]
    for i in range(4):
        rr = row + adjR[i]
        cc = col + adjC[i]
        if (rr, cc) in given:
            continue
        if isValid(rr, cc, ROWS, COLS):
            if board[rr][cc] == None or board[rr][cc] < h - 1:
                board[rr][cc] = h - 1
                arr.append((rr, cc))
    return arr

if __name__ == '__main__':
    COLS, ROWS, N = list(map(int, input().split()))

    board = [ [ None for _ in range(COLS) ] for _ in range(ROWS) ]
    plist = []

    adjR = [-1, 0, 0, 1]
    adjC = [0, -1, 1, 0]

    given = set()

    for _ in range(N):
        c, r, h = list(map(int, input().strip().split()))
        board[r - 1][c - 1] = h
        plist.append((r-1, c-1))
        given.add((r-1, c-1))

    while len(plist) > 0:
        row, col = plist.pop(0)
        updated = update(board, row, col, ROWS, COLS)
        plist.extend(updated)

    isPossible = True
    total = 0
    for r in range(ROWS):
        for c in range(COLS):
            isPossible = isPossible and not isSteep(board, r, c, ROWS, COLS)
            if not isPossible:
                break
            total += board[r][c]
        if not isPossible:
            break

    print(total if isPossible else "No")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    w,h,n = LI()
    aa = [LI() for _ in range(n)]
    q = []
    r = [[None] * w for _ in range(h)]
    for x,y,z in aa:
        r[y-1][x-1] = z
        heapq.heappush(q, (-z, (y-1,x-1)))

    v = collections.defaultdict(bool)
    while len(q):
        k, u = heapq.heappop(q)
        if v[u]:
            continue
        v[u] = True
        y = u[0]
        x = u[1]

        for dy,dx in dd:
            uy = y+dy
            ux = x+dx
            if uy < 0 or uy >= h or ux < 0 or ux >= w:
                continue
            uv = (uy,ux)
            if v[uv]:
                continue
            vd = -k - 1
            if r[uy][ux] is None:
                r[uy][ux] = vd
                heapq.heappush(q, (-vd, uv))
            else:
                if abs(r[uy][ux] + k) > 1:
                    return 'No'

    return sum(sum(_) for _ in r)


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    W, D, N = read_ints()
    M = [tuple(read_ints()) for _ in range(N)]
    ans = solve(W, D, N, M)
    if ans is None:
        print('No')
    else:
        print(ans)


def solve(W, D, N, M):
    INF = 999
    H = [[INF] * W for _ in range(D)]

    hmap = {}
    for h in range(-210, 101):
        hmap[h] = set()

    for x, y, z in M:
        x -= 1
        y -= 1
        hmap[z].add((x, y))
        H[y][x] = z

    for h in range(100, -210, -1):
        for x, y in hmap[h]:
            if H[y][x] == INF:
                H[y][x] = h
            elif H[y][x] > h:
                continue

            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= W or ny < 0 or ny >= D:
                    continue
                if H[ny][nx] < h - 1:
                    return None
                if H[ny][nx] == INF:
                    hmap[h - 1].add((nx, ny))

    return sum([sum(r) for r in H])


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()