1976. 人里的飞行轨迹

你们在下山后回到人里休息,出题人因为波奇酱附体直接呼呼大睡,于是白渃和托尔准备去天上飞一会从天上向下看人里的天地,托尔和白渃决定玩个游戏,在天上用飞行轨迹画画(人里的人:已经无所谓了)

img

把人里的天空划为 nnmm 列,记第 ii 行第 jj 列的状态为 ci,jc_{i,j}。为方便起见,设有云为 11,没云为 00。由于游戏刚开始,所有格子都是没云的,即初始时: 1in,1jm,ci,j=0 \forall 1\le i\le n,1\le j\le m,c_{i,j}=0 白渃负责在天空中制造轨迹,托尔负责消除这些轨迹。他们总是沿着一行或一列进行飞行。具体而言,有四种行为:

  1. 托尔在第 xx 行飞行,使得 1jm,cx,j=0\forall 1\le j\le m, c_{x,j}=0
  2. 白渃在第 xx 行飞行,使得 1jm,cx,j=1\forall 1\le j\le m, c_{x,j}=1
  3. 托尔在第 xx 列飞行,使得 1in,ci,x=0\forall 1\le i\le n, c_{i,x}=0
  4. 白渃在第 xx 列飞行,使得 1in,ci,x=1\forall 1\le i\le n, c_{i,x}=1

注意每次飞行形成的新轨迹会覆盖之前的飞行形成的旧轨迹。

他们通过飞行轨迹进行作画,并想知道是否能通过若干次飞行作成特定的 nnmm 列画作 aa,如果能,还想知道如何飞行能得到这样的画作。

输入

输入一行两个整数 n,m(1n,m100)n,m(1\le n,m\le 100),代表方格的行列数。

接下来输入 nn 行,每行 mm 个整数,第 ii 个整数代表 ai,j(0ai,j1)a_{i,j}(0\le a_{i,j}\le 1)

输出

如果对初始全 00cc,经由不超过 nmmax(n,m)nm\max(n,m) 次飞行可以得到 aa,则第一行输出 I can fly!,否则,输出 Sorry, I can't do that.

如果能得到 cc,接下来输入一行一个整数 t(0tnmmax(n,m))t(0\le t\le nm\max(n,m)),代表飞行总次数。并且接下来输出 tt 行,第 ii 行两个整数 wi,xi(1wi4)w_i,x_i(1\le w_i\le 4),代表第 ii 次飞行的行为类型,及飞行所在行/列。若 w2w\le 2,则 1xin1\le x_i\le n;否则,1xim1\le x_i\le m

如果有多种飞行方案能得到 aa,则输出任意一个方案即可。

样例

标准输入 复制文本
2 3
0 0 0
0 1 1
标准输出 复制文本
I can fly!
2
2 2
3 1
标准输入 复制文本
3 3
0 0 0
1 0 0
1 1 0
标准输出 复制文本
I can fly!
5
4 2
1 1
2 1
4 1
1 1
标准输入 复制文本
4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
标准输出 复制文本
Sorry, I can't do that.

提示

样例四:

3 2 0 0 0 0 0 0

I can fly! 0

对样例一,一种可行的方案为:(箭头表示 (w,x)\xrightarrow{(w,x)}) ParseError: KaTeX parse error: Expected 'EOF', got '\pmatrix' at position 2: \̲p̲m̲a̲t̲r̲i̲x̲{0&0&0\0&0&0} \… 对样例二,一种可行的方案为: ParseError: KaTeX parse error: Expected 'EOF', got '\pmatrix' at position 2: \̲p̲m̲a̲t̲r̲i̲x̲{0&0&0\0&0&0\0&… 对样例三,可以证明,穷尽所有的飞行方案,都找不到一种方案能构造出 aa

对样例四,初始就有 c=ac=a,故无需飞行即可得到。

来源

2023 SCNUCPC 重现赛

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 6
通过 3