Civilization

这是一个回合制游戏，每一回合开始前会进行上一回合的结算。

有一张 $n*n$ 的棋盘，我们出生在一个初始位置 $(x, y)$，现在我们要选择一个位置建设城市。

你的人物每回合可以移动到距离你曼哈顿距离不超过 2 的位置，移动完成后可以选择是否建立城市。

建立城市后，你的人物消失，成为一个人口为 1 的城市，这个人口要下回合才可以工作。如果不移动，直接在 (x,y) 建城，第 1 回合就可以开始工作。

对于城市的每个居民，你可以安排他到距离城市曼哈顿距离小于等于 3 的位置进行工作，此居民可以瞬间到达该位置，每个位置最多安排一个居民，失业的人口不会生产任何食物。

注意，城市位置上必须有一个居民在工作。

结算按照如下顺序：
1. 如果位置 $(i, j)$ 上有一个工作居民，则获得 $a[i][j]$ 的食物。
2. 如果当前城市人口为 $i$，且食物达到 $8*i^2$ 时，你获得一个新的居民，下一回合可以进行操作。

当结算后城市总人口达到 9 游戏结束。

初始食物数量为 0，人口上涨不会导致之前积累的食物消失。输出最少几个回合能让游戏结束。

第一行一个正整数 $test(1 \le test \le 10)$ 表示数据组数。

对于每组数据，第一行三个正整数 $n(2 \le n \le 500), x(1 \le x \le n), y(1 \le y \le n)$，分别表示棋盘大小和起始位置。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a[i][j](1 \le a[i][j] \le 3)$。

对于每组数据，一行一个整数表示答案。

1
10 9 8
1 2 2 1 2 3 1 1 2 1
2 1 3 3 3 2 3 2 3 1
1 1 3 1 1 3 2 2 1 2
3 1 3 1 3 3 1 3 1 3
3 2 3 1 3 1 2 2 2 1
2 3 2 3 2 2 3 1 2 3
3 1 3 3 2 2 3 2 3 3
1 3 3 2 3 2 2 2 1 1
3 3 1 2 3 2 1 2 1 2
1 1 3 1 3 1 1 1 3 3

39

2020 年百度之星·程序设计大赛 - 初赛一