你们在下山后回到人里休息,出题人因为波奇酱附体直接呼呼大睡,于是白渃和托尔准备去天上飞一会从天上向下看人里的天地,托尔和白渃决定玩个游戏,在天上用飞行轨迹画画(人里的人:已经无所谓了)
把人里的天空划为 n 行 m 列,记第 i 行第 j 列的状态为 c_{i,j}。为方便起见,设有云为 1,没云为 0。由于游戏刚开始,所有格子都是没云的,即初始时: \forall 1\le i\le n,1\le j\le m,c_{i,j}=0 白渃负责在天空中制造轨迹,托尔负责消除这些轨迹。他们总是沿着一行或一列进行飞行。具体而言,有四种行为:
注意每次飞行形成的新轨迹会覆盖之前的飞行形成的旧轨迹。
他们通过飞行轨迹进行作画,并想知道是否能通过若干次飞行作成特定的 n 行 m 列画作 a,如果能,还想知道如何飞行能得到这样的画作。
输入
输入一行两个整数 n,m(1\le n,m\le 100),代表方格的行列数。
接下来输入 n 行,每行 m 个整数,第 i 个整数代表 a_{i,j}(0\le a_{i,j}\le 1)。
输出
如果对初始全 0 的 c,经由不超过 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 重现赛