1976. 人里的飞行轨迹

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

img

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

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

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

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

输入

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

接下来输入 n 行,每行 m 个整数,第 i 个整数代表 a_{i,j}(0\le a_{i,j}\le 1)

输出

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

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

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

样例

标准输入 复制文本
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

对样例一,一种可行的方案为:(箭头表示 \xrightarrow{(w,x)}) \pmatrix{0&0&0\0&0&0} \xrightarrow{(2,2)} \pmatrix{0&0&0\1&1&1} \xrightarrow{(3,1)} \pmatrix{0&0&0\0&1&1} 对样例二,一种可行的方案为: \pmatrix{0&0&0\0&0&0\0&0&0} \xrightarrow{(4,2)} \pmatrix{0&1&0\0&1&0\0&1&0} \xrightarrow{(1,1)} \pmatrix{0&0&0\0&1&0\0&1&0} \xrightarrow{(2,1)} \pmatrix{0&0&0\0&0&0\0&1&0} \xrightarrow{(4,1)} \pmatrix{1&0&0\1&0&0\1&1&0} \xrightarrow{(1,1)} \pmatrix{0&0&0\1&0&0\1&1&0} 对样例三,可以证明,穷尽所有的飞行方案,都找不到一种方案能构造出 a

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

来源

2023 SCNUCPC 重现赛

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