P13475 [GCJ 2008 APAC SemiFinal] Apocalypse Soon

糟糕！世界脆弱的政治平衡终于崩溃了，每个国家都向其他国家宣战。你曾经警告过所有愿意倾听的人会发生这种事，但他们有听进去吗？哈！现在你唯一能指望的就是尽可能活得久一点。 幸运的是（某种意义上），所有国家的工业中心都已经被摧毁，所以每个国家唯一的攻击方式就是不断地向邻国派遣一波又一波的征召士兵。这意味着每个国家只能攻击它的直接邻国。世界是一个 $R$ 行 $C$ 列的网格，行号从最北边的 $1$ 到最南边的 $R$，列号从最西边的 $1$ 到最东边的 $C$。每个国家占据网格上的一个格子，这意味着每个国家最多可以接触到 4 个相邻的国家。 每个国家一开始都有一个已知的特定实力值。它们没有高级战略的概念，所以每天一开始，它们会简单地选择自己最强的邻国（如有并列，优先选择最北边的国家，再优先选择最西边的），然后派出军队攻击。军队的攻击力等于该国当前的实力 $S$；到当天结束时，被攻击邻国的实力会减少 $S$。如果一个国家的实力降到 $0$，它就会被摧毁。注意，所有国家会同时发动攻击；无论当天是否被攻击，军队的攻击力都不会改变。 你的国家位于 $(c, r)$，即第 $r$ 行第 $c$ 列。幸运的是，你的国家会听从你的建议，所以你不必遵循这种疯狂的策略。你每天可以选择攻击任意一个邻国（也可以什么都不做）。不过你不能同时攻击多个邻国，也不能用小于全部实力的军队攻击。 请你判断，你最多能存活多少天。

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含四个整数 $C$、$R$、$c$ 和 $r$。接下来的 $R$ 行，每行包含 $C$ 个整数，表示每个国家的初始实力 $S_{c_i,r_i}$，其中 $ci$ 表示列号，$ri$ 表示行号。若某国的实力为 $0$，表示该国已经被摧毁。你的国家的初始实力不会为 $0$。

对于每组测试数据，输出一行，格式为 "Case #A: "，后接： - "B day(s)"，其中 $B$ 表示你最多能存活的天数。 - 如果你能比所有邻国都活得久，输出 "forever"。

**数据范围** - $1 \leq T \leq 100$ - $1 \leq c \leq C$ - $1 \leq r \leq R$ **小数据范围（8 分，测试点 1 - 可见）** - $1 \leq C \leq 5$ - $1 \leq R \leq 5$ - $0 \leq S_{c_i,r_i} \leq 10$ **大数据范围（14 分，测试点 2 - 隐藏）** - $1 \leq C \leq 50$ - $1 \leq R \leq 50$ - $0 \leq S_{c_i,r_i} \leq 1000$ 由 ChatGPT 4.1 翻译