题解 CF1668A【Direction Change】

## 题意 有一个大小为 $n \times m$ 的棋盘。你一开始位于左上角 $(1, 1)$，想要走到右下角 $(n, m)$。 每步可以上下左右四个方向移动。但是不能出界，也**不能连续两次朝着相同方向移动**。问到达目的地的最小步数。 ## 思路 首先思考什么情况下无法达到目的地。当棋盘大小为 $1 \times x (x > 2)$ 的时候，要想不出界，就必须朝着目的地方向移动至少两步，与题意矛盾，故此时无法到达目标。 否则一定可以到达目的地。 - 当 $n = m$ 时，走**对角线**就是最优方案（右-下-右-下…），总共需要 $2 \times (n - 1)$ 步 - 若 $n \not = m$，不妨假设 $n <= m$。首先还是沿 $45$ 度角方向，斜向下走到最远的位置，消耗 $2 \times (n - 1)$ 步；剩下 $m-n$ 个格子横着走。为了满足题目要求，最后这一段需要上下摆动行走，以避免连续两步方向相同。需要区分剩余步数是奇数还是偶数。剩余奇数步的话可以少摆动一次。 ## 代码 ```cpp void solution() { int n, m; read(n, m); if (n == 1 && m > 2) return print(-1); if (m == 1 && n > 2) return print(-1); if (n == m) return print(2 * (n - 1)); if (n > m) std::swap(n, m); int ans = (n - 1) * 2; ans += (m - n) * 2; if ((m - n) & 1) ans -= 1; print(ans); } ```