题解 | 等差数列

from sys import stderr, stdout

stderr = stdout


def calc(up):
    i0, v0 = up[0]
    i1, v1 = up[1]
    k = (v1 - v0) // (i1 - i0)
    b = v0 - i0 * k
    return (k, b)


def main():
    n, m = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(n)]
    # print(n, m, *mat, sep="\n", file=stderr)

    rec = [[0] * m for _ in range(n)]
    yup = [[] for _ in range(n)]
    xup = [[] for _ in range(m)]
    upd = []
    upe = []

    def update(y: int, x: int, v: int):
        nonlocal upd
        # print(y, x, v, file=stderr)
        assert v, (y, x, v)
        if rec[y][x] == 0:
            ryup = yup[y]
            rxup = xup[x]
            if ryup is not None and len(ryup) < 2:
                ryup.append((x, v))
                if len(ryup) == 2:
                    upd.append(("y", y))
            if rxup is not None and len(rxup) < 2:
                rxup.append((y, v))
                if len(rxup) == 2:
                    upd.append(("x", x))
            rec[y][x] = v
        else:
            assert rec[y][x] == v, (rec[y][x], v)

    # initial
    for y, row in enumerate(mat):
        for x, val in enumerate(row):
            if val:
                update(y, x, val)

    # iterate
    while len(upd) > 0:
        # print(f'-- BEFORE --', file=stderr)
        # print(*rec, sep='\n', file=stderr)
        upe.clear()
        upd, upe = upe, upd
        for c, i in upe:
            if c == "y":
                # print(c, i, yup[i], file=stderr)
                k, b = calc(yup[i])
                for x in range(0, m):
                    update(i, x, k * x + b)
            else:
                # print(c, i, xup[i], file=stderr)
                k, b = calc(xup[i])
                for y in range(0, n):
                    update(y, i, k * y + b)
        # print('-- AFTER --', file=stderr)
        # print(*rec, sep="\n", file=stderr)

    for y, row in enumerate(mat):
        for x, val in enumerate(row):
            if val == 0 and rec[y][x]:
                print(y + 1, x + 1, rec[y][x])


main()

只要某一行(列)有2个元素，就可确定整行(列)。

之后可能使其他行(列)新增元素，需反复，直到不能再确定新的行(列)。

最后与最初状态比较，输出从零变非零的元素。