309362: CF1668A. Direction Change

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Direction Change

题意翻译

### 题目描述: 有一个 $n \times m$ 的矩阵,现在你在 $( 1,1 )$,你可以朝上、下、左、右四个方向移动,但不可以连续朝某个方向移动,问最少需要移动几次你才可以到达 $( n,m )$,如果无法到达 $( n,m )$,输出 $-1$。 ### 输入格式: 第一行一个整数 $t ( 1\le t \le 10^3 )$,表示有 $t$ 组询问。 接下来 $t$ 行,每行两个整数,表示 $n$ 和 $m ( 1\le n,m \le 10^9 )$。 ### 输出格式: 对于每一组询问,输出对应的答案。 ### 说明/提示 样例第一组询问:不需要移动。 样例第二组询问:向下移动一次。 样例第三组询问:不能到达。 样例第四组询问:有一种可行的解法为 $(1,1)\to(1,2)\to(2,2)\to(2,1)\to(3,1)\to(3,2)\to(4,2)$,共 $6$ 步。

题目描述

You are given a grid with $ n $ rows and $ m $ columns. Rows and columns are numbered from $ 1 $ to $ n $ , and from $ 1 $ to $ m $ . The intersection of the $ a $ -th row and $ b $ -th column is denoted by $ (a, b) $ . Initially, you are standing in the top left corner $ (1, 1) $ . Your goal is to reach the bottom right corner $ (n, m) $ . You can move in four directions from $ (a, b) $ : up to $ (a-1, b) $ , down to $ (a+1, b) $ , left to $ (a, b-1) $ or right to $ (a, b+1) $ . You cannot move in the same direction in two consecutive moves, and you cannot leave the grid. What is the minimum number of moves to reach $ (n, m) $ ?

输入输出格式

输入格式


The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of the test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^9 $ ) — the size of the grid.

输出格式


For each test case, print a single integer: $ -1 $ if it is impossible to reach $ (n, m) $ under the given conditions, otherwise the minimum number of moves.

输入输出样例

输入样例 #1

6
1 1
2 1
1 3
4 2
4 6
10 5

输出样例 #1

0
1
-1
6
10
17

说明

Test case $ 1 $ : $ n=1 $ , $ m=1 $ , and initially you are standing in $ (1, 1) $ so $ 0 $ move is required to reach $ (n, m) = (1, 1) $ . Test case $ 2 $ : you should go down to reach $ (2, 1) $ . Test case $ 3 $ : it is impossible to reach $ (1, 3) $ without moving right two consecutive times, or without leaving the grid. Test case $ 4 $ : an optimal moving sequence could be: $ (1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2) $ . It can be proved that this is the optimal solution. So the answer is $ 6 $ .

Input

题意翻译

### 题目描述: 有一个 $n \times m$ 的矩阵,现在你在 $( 1,1 )$,你可以朝上、下、左、右四个方向移动,但不可以连续朝某个方向移动,问最少需要移动几次你才可以到达 $( n,m )$,如果无法到达 $( n,m )$,输出 $-1$。 ### 输入格式: 第一行一个整数 $t ( 1\le t \le 10^3 )$,表示有 $t$ 组询问。 接下来 $t$ 行,每行两个整数,表示 $n$ 和 $m ( 1\le n,m \le 10^9 )$。 ### 输出格式: 对于每一组询问,输出对应的答案。 ### 说明/提示 样例第一组询问:不需要移动。 样例第二组询问:向下移动一次。 样例第三组询问:不能到达。 样例第四组询问:有一种可行的解法为 $(1,1)\to(1,2)\to(2,2)\to(2,1)\to(3,1)\to(3,2)\to(4,2)$,共 $6$ 步。

加入题单

上一题 下一题 算法标签: