给定一个N×N的棋盘和一个只能在两个方向上移动一步的白王：右和上。

Question

给定一个N×N的棋盘和一个只能向两个方向移动一步的白王：右和上。假设国王在起始位置的左下角）。而且，一旦国王开始移动，它只能改变一次方向。例如，如果它开始向右移动第一步，它可以继续向右移动，或者在某一时刻转而向上移动。此后，它不能再向右移动。给予国王'n'步棋，它在棋盘上最多可以到达或通过多少个不同的格子？设计一个合适的算法来解决这个问题，并计算其运行时间。

Answer 1

答案是 (n * (n + 1))/ 2 + n - 1 方格。

你只需要观察可能性与小 n 值来验证。

让我们看看一些小的 ns:

n = 3     n = 4       n = 5         n = 6      ...

x x o    x x o o    x x o o o    x x o o o o
x x x    x x x o    x x x o o    x x x o o o
s x x    x x x x    x x x x o    x x x x o o
         s x x x    x x x x x    x x x x x o
                    s x x x x    x x x x x x
                                 s x x x x x

s: where king starts
x: squares he can reach
o: squares he cannot reach

很容易看出，他到达了矩阵的左下半部分，加上对角线的数量。n - 1 方块。

n = 6

x\ x \ o o o o
xx\ x \ o o o
xxx\ x \ o o
xxxx\ x \ o
xxxxx\ x \
sxxxxx\   \

(n*(n+1))/2 + (n-1)