Точка выхода в бинарной матрице
Учитывая бинарную матрицу размера N x M , вы вводите матрицу в ячейку (0, 0) в направлении слева направо. Всякий раз, когда встречается 0, сохраняйте в том же направлении, если встречается 1, измените направление вправо от текущего направления и измените это значение 1 на 0, найдите точку выхода из матрицы.
Примеры:
Input: matrix = {{0, 1, 0},
{0, 1, 1},
{0, 0, 0}}
Output: 1 0
Explanation:
Enter the matrix at 0, 0 -> then move towards 0, 1 -> 1 is encountered -> turn right towards 1, 1 -> again 1 is encountered -> turn right again towards 1, 0 -> now, the boundary of matrix will be crossed ->hence, exit point reached at 1, 0.
Input: matrix = {{0, 0}}
Output: 0 1
Подход: поскольку матрица вводится в позиции 0, 0, подход к решению этой проблемы основан на следующих наблюдениях.
- Первоначально матрица вводится в 0, 0 и перемещается вправо.
- Как только встречается 1, направление поворачивается на 90 градусов по часовой стрелке, то есть вправо -> вниз -> влево -> вверх.
- Продолжайте перемещаться по матрице вышеупомянутым образом, пока не будет достигнута граница.
- Как только граница будет достигнута и поворот не встретится, граница будет пересечена, а точкой выхода будет последняя пройденная ячейка.
Иллюстрация:
Consider the matrix:
{{0, 1, 0},
{0, 1, 1},
{0, 0, 0}}
- Traverse the matrix using row as i and column as j.
- Initially the matrix is entered at 0, 0 and moved towards right ( (i, j) -> (i, j++) ) till 1 is encountered.
- 1 is encountered at 1, 0. So, direction will be changed 90 degrees clockwise towards down ( (i, j) -> (i++, j) ).
- Keep moving down till 1 is encountered at 1, 1
- Again direction will be changed 90 degrees towards left ( (i, j) -> (i, j–) ).
- Keep moving left.
- No 1 is encountered now but the boundary of the matrix is crossed at 1, 0 and hence, 1, 0 is the required exit point.
Ниже приведена реализация вышеупомянутого подхода:
Временная сложность: O(NxM), где N — количество строк, а M — количество столбцов.
Вспомогательное пространство: O(1)