Проверить, можно ли добраться до соседней ячейки Start, посетив все ячейки один раз

Опубликовано: 14 Февраля, 2023

Учитывая два целых числа X и Y , которые представляют количество строк и столбцов матрицы соответственно, задача состоит в том, чтобы проверить, существует ли путь, который соответствует всем нижеприведенным условиям:

  • Начало пути из ячейки (1, 1) .
  • Концом пути является любая ячейка, примыкающая к (1, 1) .
  • Вы должны пройти через каждую ячейку матрицы только один раз.

Примечание. Здесь используется индексация на основе 1.

Примеры:

Input:  X = 2, Y = 3
Output: YES
Explanation:

Explanation for input test case

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:

Explanation for test case 1

Test case 2:  X=4, Y=5
Output: YES
Explanation:

Explanation for test case 2

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)