NowCoder 203A – Knight (搜索/贪心)

Table of Contents

题意

无限大的棋盘,每次移动都是“日”字对角线形移动$(+1,+2)$,问你走到目的地的最小移动次数。

思路

目的地$(x,y)$可能非常远,直接搜索肯定boom,所以先贪心把距离减小然后再小范围地搜索。之后就各种RE WA反正做不对……

上网搜索题解之后发现这题可以完全不搜索直接贪心。

首先棋盘是完全对称的,可以改成只往右上方走,因为只能沿着日字形对角线走,所以可以再缩小范围,只对$y=x$上方的区域求解。首先沿着$y=2x$一路向上窜,然后:

  • 终点在$y=2x$上方的,用$(+1,+2)$和$(-1,+2)$重复向上直到距离终点纵向距离$<4$。
    • 距离为1,撤销一次$(-1,+2)$(或$(+1,+2)$),此时距离终点$(1,3)$,两步可以解决。
    • 距离为2,多走两步$(+2,+1)$和$(-2,+1)$解决。
    • 距离为3,多走三步$(+1,+2)$,$(+1,+2)$和$(-2,-1)$解决。
  • 终点在$y=2x$右侧的,把刚才的$(+1,+2)$改成两次$(+2,+1)$,直到横向距离$<3$。
    • 距离为1,撤销一次$(+2,+1)$,距离终点$(3,1)$,两步解决。
    • 距离为2,多走两步$(+1,+2)$和$(+1,-2)$解决。

然后WA了。emmm 治疗眼瞎之后发现有两个点$(1,3)$和$(2,2)$不满足上述条件(没有可以撤销的),需要特判。最后-10过了。

代码

#include <bits/stdc++.h>
using namespace std;
 
int solve(int x, int y) {
  if (x == 0 && y == 1) {
    return 3;
  } else if (x == 2 && y == 2) {
    return 4;
  } else {
    int st = 0, ret = 0;
    if (y >= 2 * x) {
      st = x, x -= st, y -= 2 * st, ret += st;
      st = y / 4, y -= st * 4, ret += st * 2;
      assert(x == 0);
      ret += y;
    } else {
      if (y & 1) {
        st = 1, x -= 2, y -= 1, ret += st;
      }
      st = y / 2, x -= st, y -= 2 * st, ret += st;
      st = x / 3, x -= st * 3, ret += st; // substitution
      ret += x;
    }
    return ret;
  }
}
 
int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    int x = 0, y = 0;
    scanf("%d%d", &x, &y);
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    if (x > y) swap(x, y);
    printf("%d\n", solve(x, y));
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注