Challenge from Grandfather

Time Limit : 2 sec, Memory Limit : 65536 KB

Problem B: Challenge from Grandfather

Problem

祖父から1と0だけが書かれたn×nの行列とm個の操作が書かれている紙が送られてきた。

紙の裏を見てみると、「この紙に書いてある行列に操作を加えて新しくできた行列をわしのとこに送ってくるのじゃ! 一流のプログラマになりたいならこれくらいできなきゃ話にならんぞ!」と書かれている。どうやら私への挑戦状らしい。 しかし私はプログラマではなくパティシエになりたいため、プログラムを書いたこ とがない。祖父にそのことを何度も言っているが一向に聞く耳を持ってくれない。 そこで、私の友達であるあなたにこの問題を解決するプログラムを組んでもらいたい。以下に操作の種類を示す。


部分行列と角度(0,90,180,270,360)が与えられるのでその分だけ時計回りに回転させる。

部分行列が与えられるので値を反転させる。

行が与えられるので左に1個シフトし、はみ出た分は右端に移動する。

行が与えられるので右に1個シフトし、はみ出た分は左端に移動する。

行(r),列(c)が与えられる。
Step1:現在のセルを(r,c)にする。
Step2:現在のセルの値を反転する。
Step3:隣接するセルのうち、値が現在のセルの反転前の値と等しいセルに対し、Step2とStep3の処理を行う。
ここで、セル(i,j)に隣接するセルとは、(i-1,j), (i+1,j),(i,j-1),(i,j+1)の4つである。

Input

n m
a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an,n
Operation1
Operation2
:
Operationm

入力の最初に2つの整数nmが空白区切りで与えられる。 nは行列のサイズ、mは操作の数を表している。

次にグリッドの情報がn行で与えられ、グリッドの情報のi行目にはn個の整数 ai,jが空白区切りで与えられる。ai,jには0か1が与えられる。

次に1行で表される各Operationim個与えられる。 Operationi の最初の入力はo(操作の種類)が入力される。

oが0のときは回転(Rotate)を表している。 続く入力は、r c size angle(行、列、サイズ、角度) が空白区切りで与えられる。 左上(r,c)から右下(r+size-1,c+size-1)が部分行列となる。 正方行列になることは保証されている。

oが1のときは反転(Reversal)を表している。 また、続く入力は、r c size (行、列、サイズ) が空白区切りで与えられる。 左上(r,c)から右下(r+size-1,c+size-1)が部分行列となる。 正方行列になることは保証されている。

oが2のときは左シフト(Left shift)を表している。 また、続く入力は r(行) が与えられる。

oが3のときは右シフト(Right shift)を表している。 また、続く入力は r(行) が与えられる。

oが4のときは島反転(Island reversal)を表している。 また、続く入力は r c(行、列) が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ n,r,c,size ≤ 15
  • 1 ≤ m ≤ 100
  • 0 ≤ o ≤ 4
  • 1 ≤ r+size-1,c+size-1 ≤ 15
  • 0 ≤ angle ≤ 360

Output

生成された行列を出力して下さい。

Sample Input 1

3 1
1 1 0
0 1 1
1 0 1
0 2 2 2 90

Sample Output 1

1 1 0
0 0 1
1 1 1

Sample Input 2

5 2
0 0 0 0 0
1 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
3 2
4 2 2

Sample Output 2

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Sample Input 3

5 2
1 1 1 0 1
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
0 1 1 1 0
1 3 3 3
0 1 1 5 90

Sample Output 3

0 0 0 1 1
1 1 0 0 1
0 1 1 0 1
0 1 0 0 0
1 1 0 0 1

Source: University of Aizu Programming Contest 2013 , Aizu Commpetitive Programming Camp 2013 Day 2, Japan, 2013-09-04