Дана сетка, состоящая из \(n\) строк и \(m\) столбцов. Строки и столбцы пронумерованы от \(1\) до \(n\) и от \(1\) до \(m\) соответственно. Пересечение \(a\)-й строки и \(b\)-го столбца обозначим за \((a, b)\).
Изначально вы находитесь в верхнем левом углу \((1, 1)\). Ваша цель — добраться до нижнего правого угла \((n, m)\)
Из клетки \((a, b)\) вы можете двигаться в четырех направлениях: вверх в клетку \((a-1, b)\), вниз в \((a+1, b)\), влево в \((a, b-1)\) или вправо в \((a, b+1)\)
Вам запрещается двигаться в одном направлении дважды подряд, вы не можете покидать пределы сетки. За какое минимальное количество шагов можно добраться до \((n, m)\)?
Выходные данные
Для каждого набора входных данных выведите одно целое число: \(-1\), если нельзя добраться до \((n, m)\) при заданных ограничениях, в ином случае — минимальное количество шагов.
Примечание
\(1\)-й набор входных данных: \(n=1\), \(m=1\), изначально вы находитесь в \((1, 1)\), поэтому \(0\) шагов необходимо, чтобы добраться до \((n, m) = (1, 1)\) .
\(2\)-й набор: нужно сделать один шаг вниз, чтобы достичь \((2, 1)\).
\(3\)-й набор: невозможно достичь \((1, 3)\), не сделав подряд два шага вправо или не покидая пределы сетки.
\(4\)-й набор: оптимальная последовательность шагов выглядит например так: \((1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)\). Можно доказать, что это оптимальное решение. Таким образом, ответ равен \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
2 1
1 3
4 2
4 6
10 5
|
0
1
-1
6
10
17
|