【python】CodingGames Shadows of the Knight - Episode 1

描述：
你是蝙蝠侠，你将通过使用你的抓斗枪从一个窗口跳到另一个窗口来寻找给定建筑物上的人质。您的目标是跳到人质所在的窗口以解除炸弹的武装。不幸的是，在炸弹爆炸之前你的跳跃次数是有限的……

在每次跳跃之前，热信号装置会根据您当前的位置为您提供炸弹的方向：（八个）

初始化输入：

第 1 行： 2 个整数W H. 这 （W,H) 对将建筑物的宽度和高度表示为多个窗户。
第 2 行： 1 个整数n，它代表你在炸弹爆炸之前可以跳的次数。
第 3 行： 2 个整数X0 Y0，代表你的起始位置。

这题简单做法是直接按照提供方向一步一步前进，但是显而易见效率很低。

import sys
import math

# w: width of the building.
# h: height of the building.
w, h = [int(i) for i in input().split()]
n = int(input())  # maximum number of turns before game over.
x0, y0 = [int(i) for i in input().split()]

# game loop
while True:
    bomb_dir = input()  # the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)

    if bomb_dir == "U":
        y0 -= 1
    elif bomb_dir == "UR":
        x0 += 1
        y0 -= 1
    elif bomb_dir == "R":
        x0 += 1
    elif bomb_dir == "DR":
        x0 += 1
        y0 += 1
    elif bomb_dir == "D":
        y0 += 1
    elif bomb_dir == "DL":
        x0 -= 1
        y0 += 1
    elif bomb_dir == "L":
        x0 -= 1
    else:
        x0 -= 1
        y0 -= 1

    # the location of the next window Batman should jump to.
    print("%d %d" %(x0, y0))

更好的办法是按边界范围收缩，因为老爷无所不能！哪都能跳，我们只要能保证最后范围收缩的中心点是目标点就好！

• 设置Xmin，Ymin，Xmax，Ymax，分别表示（0,0)点 和(W-1, H-1) 两个端点

• 按照系统提供的方向更新(Xmin,Ymin), (Xmax, Ymax)的位置，让范围向目标靠拢

  比如人质在老爷右上方，就可以把xmin 和 ymax 边界设置在老爷的右上角

• 老爷每次跳在范围的中心点

import sys
import math

# w: width of the building.
# h: height of the building.
w, h = [int(i) for i in input().split()]
n = int(input())  # maximum number of turns before game over.
x0, y0 = [int(i) for i in input().split()]
x_min, y_min = 0, 0
x_max, y_max = w - 1, h - 1

# game loop
while True:
    bomb_dir = input()  # the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)

    if bomb_dir == "U":
        y_max = y0 - 1
        y0 = (y_min + y_max) // 2
    elif bomb_dir == "UR":
        x_min = x0 + 1
        y_max = y0 - 1
        x0 = (x_min + x_max) // 2
        y0 = (y_min + y_max) // 2
    elif bomb_dir == "R":
        x_min = x0 + 1
        x0 = (x_min + x_max) // 2
    elif bomb_dir == "DR":
        x_min = x0 + 1
        y_min = y0 + 1
        x0 = (x_min + x_max) // 2
        y0 = (y_min + y_max) // 2
    elif bomb_dir == "D":
        y_min = y0 + 1
        y0 = (y_min + y_max) // 2
    elif bomb_dir == "DL":
        x_max = x0 - 1
        y_min = y0 + 1
        x0 = (x_min + x_max) // 2
        y0 = (y_min + y_max) // 2
    elif bomb_dir == "L":
        x_max = x0 - 1
        x0 = (x_min + x_max) // 2
    else:
        x_max = x0 - 1
        y_max = y0 + 1
        x0 = (x_min + x_max) // 2
        y0 = (y_min + y_max) // 2

    # the location of the next window Batman should jump to.
    print("%d %d" %(x0, y0))

在Tower中老爷反复横跳的样子让我幻视SGD……

本质上是个二分问题。