Будем строить набор максимально возможных глубин, то есть такой, что $$$-1$$$ в каждой ячейке заменяется на наибольшее число, не нарушающее при этом никаких условий задачи.

Заметим, что каждое известное (не равное $$$-1$$$) значение глубины $$$d_{ij}$$$ в некоторой ячейке $$$(i,j)$$$ порождает множество ограничений на максимальную глубину во всех других ячейках. А именно, ячейки, находящиеся от $$$(i,j)$$$ на манхэттенском расстоянии, равном 1, не могут иметь глубину больше, чем $$$d_{ij} + v$$$. Ячейки, находящиеся на манхэттенском расстоянии $$$2$$$, не могут иметь глубину больше, чем $$$d_{ij} + 2\cdot v$$$, и так далее. Если глубина в некоторой ячейке нарушает хотя бы одно из ограничений, то она не может являться частью корректного ответа. То есть, значение в любой ячейке должно удовлетворять наиболее строгому (минимальному по величине) из ограничений в ней. Обозначим его $$$dmax_{ij}$$$.

Покажем, что значения $$$dmax_{ij}$$$ в любых соседних ячейках не могут отличаться больше, чем на $$$v$$$. Предположим обратное: нашлась какая-то пара значений $$$d_1$$$ и $$$d_2$$$, такая что $$$d_1 > d_2 + v$$$. Поскольку $$$d_2$$$ — это просто минимум из ограничений в ячейке, то существует какое-то ограничение, на котором этот минимум достигается. Рассмотрим ограничения на соседние ячейки, порожденные тем же значением $$$d_{ij}$$$. Поскольку манхэттенское расстояние до соседних клеток отличается ровно на 1, то эти ограничения могут быть равны $$$d_2+v$$$ или $$$d_2-v$$$. В любом случае, имеем значения не больше $$$d_2+v$$$. А значит, и минимум из всех ограничений в любой из соседних клеток не может превосходить этой величины. Получили противоречие с тем, что $$$d_1 > d_2 + v$$$. Значит, построенный таким образом набор глубин $$$dmax_{ij}$$$ удовлетворяет условию задачи: разность любых соседних значений не превосходит $$$v$$$.

Заметим, что рассуждение выше верно только в том случае, если все уже известные глубины удовлетворяют всем ограничениям, порожденным другими глубинами. Если же в некоторой ячейке $$$d_{ij} > dmax_{ij}$$$, то существуют какие-то две ячейки, находящиеся на манхэттенском расстоянии $$$x$$$ и имеющие разность глубин больше, чем $$$v \cdot x$$$. В этом случае построить требуемое невозможно.

Покажем, как можно эффективно вычислять $$$dmax_{ij}$$$. Разобьем все ограничения, существующие в ячейке $$$(i,j)$$$, на следующие группы:

• ограничения, порожденные значениями в ячейках слева сверху от $$$(i,j)$$$, то есть такими, что их индексы $$$(i', j')$$$ удовлетворяют условиям $$$i' \leq i$$$, $$$j' \leq j$$$;
• ограничения, порожденные значениями справа сверху от $$$(i,j)$$$ ($$$i' \leq i$$$, $$$j' \geq j$$$);
• ограничения, порожденные значениями слева снизу от $$$(i,j)$$$ ($$$i' \geq i$$$, $$$j' \leq j$$$);
• ограничения, порожденные значениями справа снизу от $$$(i,j)$$$ ($$$i' \geq i$$$, $$$j' \geq j$$$).

Очевидно, что любое из ограничений попадает как минимум в одну из групп.

Соответственно, запустим несколько отдельных проходов по таблице: слева сверху, справа сверху, слева снизу и справа снизу. При каждом проходе будем вычислять $$$dmax_{ij}$$$ с учетом ограничений только выбранной группы. Значения пересчитываются на основе значений соседей, уже вычисленных ранее в том же проходе. Например, при проходе слева сверху: $$$$$$ dmax[i][j] = min(dmax[i-1][j] + v, dmax[i][j-1] + v). $$$$$$ Если хотя бы в одном из проходов в любой из ячеек мы получим $$$d_{ij} > dmax_{ij}$$$, то ответ к задаче NO. В противном случае (противоречий не обнаружилось) —YES.