Минимальное количество подсказок, необходимых для получения скрытой ячейки в 2D-сетке

Дан двумерный массив размера M * N . Задача состоит в том, чтобы найти минимальное количество подсказок, необходимых для выбора правильного положения скрытой ячейки на сетке, где в каждой подсказке будет сообщено манхэттенское расстояние скрытой ячейки от любой выбранной ячейки.

Примечание. Манхэттенское расстояние между двумя ячейками представляет собой сумму абсолютных разностей между строками и столбцами ячеек.

Примеры:

Input: M = 1, N = 3
Output: 1
Explanation: For any hidden cell , if X-path distance from (1,1) is known, then hidden cell is (1, 1+X).

Input: M = 1, N = 1
Output: 0
Explanation: Only one possible cell.

Подход: Есть три возможных случая, чтобы найти положение ячейки на сетке:

Случай-1: когда сетка имеет форму строки, т.е. размер = (1 x N)

Для приведенной выше таблицы требуется как минимум одна подсказка. В подсказке можно получить расстояние от ячеек (1, 1) , и если X — расстояние скрытой ячейки от (1, 1), то (1, 1+X ) будет скрытой ячейкой.

Случай 2: когда сетка имеет форму столбца, т.е. размер = (N x 1)

Для приведенной выше таблицы требуется как минимум одна подсказка. В подсказке можно получить расстояние от (1, 1) и если X расстояние скрытой ячейки от (1, 1), то (1+X, 1) будет скрытой ячейкой.

Случай 3: когда сетка имеет прямоугольную форму, т.е. размер = (M x N)
Для этого типа таблиц требуется как минимум две подсказки. Необходимые подсказки показаны ниже:

1. Один, чтобы получить расстояние пути от ячейки (1, 1), и если X - расстояние пути скрытой ячейки от (1, 1), то любая ячейка формы (1+X ₁ , 1+X ₂ ) будет скрытой ячейка, где X ₁ + X ₂ = X .
2. Другой, чтобы получить расстояние пути от ячейки (1, N), и если Y - расстояние пути скрытой ячейки от (1, N), то любая ячейка формы (1 + Y ₁ , NY ₂ ) будет скрытой ячейкой где Y ₁ + Y ₂ = Y .

Для любой комбинации X и Y существует только одна ячейка, которая удовлетворяет обоим расстояниям. Используя два приведенных выше уравнения, можно легко найти скрытую ячейку. Таким образом, в этом случае потребуется как минимум две единицы помощи.

Следуйте изображению ниже, чтобы лучше понять условия и пересечение ячеек с любыми значениями X и Y. Любое значение X и Y будет иметь только одну ячейку в качестве точки пересечения.

равноудаленные клетки от 1,1

равноудаленная ячейка от (1,N), т.е. 1,4

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)