Проверить, можно ли добраться до соседней ячейки Start, посетив все ячейки один раз
Учитывая два целых числа X и Y , которые представляют количество строк и столбцов матрицы соответственно, задача состоит в том, чтобы проверить, существует ли путь, который соответствует всем нижеприведенным условиям:
- Начало пути из ячейки (1, 1) .
- Концом пути является любая ячейка, примыкающая к (1, 1) .
- Вы должны пройти через каждую ячейку матрицы только один раз.
Примечание. Здесь используется индексация на основе 1.
Примеры:
Input: X = 2, Y = 3
Output: YES
Explanation:Each cell is traversed once, starting cell is (1, 1) and ending cell is (2, 1), Which is adjacent to (1, 1). Hence, all the conditions met.
Input: X = 1, Y = 1
Output: NO
Explanation: As there is no adjacent cell of ( 1, 1 ) exists therefore, Output is NO.
Подход: Задача может быть решена на основе следующего наблюдения:
Наблюдение:
Let’s take some random test-cases.
Test case 1: X = 4, Y = 4
Output: YES
Explanation:Test case 2: X=4, Y=5
Output: YES
Explanation:Test case 3: X = 1, Y =3
Output: NO
Explanation: No path is possible that satisfy given constraints.From all above test cases, We can conclude some conditions:
- If both X and Y are odd, Then there exists no path.
- If (X = 1 && Y > 2) or (Y = 1 && X > 2), Then no path exists.
- All the cases except above discussed 2( number 1 and number 2 ) cases will have a path.
Для реализации идеи выполните следующие шаги:
- Проверьте условия для X и Y , описанные выше.
- Если значения соответствуют любому из первых двух условий, путь невозможен.
- В противном случае путь существует.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(1)
Вспомогательное пространство: O(1)