AT_arc207_d [ARC207D] Devourers and Cake
题目描述
Taro the First 和 Jiro the Second 买了一个矩形蛋糕作为送给母亲的礼物。他们很饿,于是决定把蛋糕除了留给母亲的一块之外全部吃掉。
有一个蛋糕,由 $N$ 行 $M$ 列的若干块组成。对于第 $i$ 行第 $j$ 列的蛋糕块,若 $s_{i,j}$ 为 `1`,表示上面有一颗草莓,若为 `0`,则没有。
两人轮流操作,Taro the First 先开始,直到只剩下一块蛋糕为止。每次操作可以选择执行以下操作之一,但不能执行会吃掉所有剩余蛋糕块的操作。
- 吃掉最上面一行的所有蛋糕块
- 吃掉最下面一行的所有蛋糕块
- 吃掉最左边一列的所有蛋糕块
- 吃掉最右边一列的所有蛋糕块
Taro the First 希望最后留下带有草莓的一块,Jiro the Second 希望最后留下没有草莓的一块。请判断:若 Taro the First 操作得当,他是否能无论 Jiro the Second 如何操作,都保证最后剩下的一块带有草莓。
你需要回答 $T$ 组测试数据,每组输入一个蛋糕,输出答案。
输入格式
输入由标准输入给出,格式如下:
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
每组测试数据的格式如下:
$N$ $M$
$s_1$
$s_2$
$\vdots$
$s_N$
输出格式
输出 $T$ 行。
第 $i$ 行输出第 $i$ 组测试数据的答案。若 Taro the First 能保证留下带有草莓的一块,输出 `First`,否则输出 `Second`。
说明/提示
### 样例解释 1
对于第一组数据,无论 Taro 如何操作,Jiro 都可以保证留下最后一块没有草莓的蛋糕块。
对于第二组数据,如果 Taro 操作得当,他可以保证无论 Jiro 如何操作,最后剩下带有草莓的一块。
注意,不能选择把所有剩下蛋糕块都吃掉的操作。
### 数据范围
- $1 \leq T \leq 10^5$
- $1 \leq N, M \leq 10^3$
- $1 < NM$
- $s_{i}$ 是长度为 $M$ 且仅包含 `0` 和 `1` 的字符串
- 所有测试数据中 $NM$ 之和不超过 $10^6$。
由 ChatGPT 5 翻译