POJ 3106 - Flip and Turn

http://poj.org/problem?id=3106

概要

\(m\) 行 \(n\) 列の行列が与えられる． 以下のような命令の列が与えられるので，命令を左から順に処理した後の行列を答える．

• 1 左上から右下への対角線に関して転置
• 2 右上から左下への対角線に関して転置
• H 行について上下反転
• V 列について左右反転
• A, B, C 時計回りの方向にそれぞれ 90度，180度，270度回転
• X, Y, Z 反時計回りの方向にそれぞれ 90度，180度，270度回転

制約

• \(0 < m, n \le 300\)
• \(0 < \mbox{命令の数} \le 10^5\)

解法

どの命令も行列として表現できるので命令は結合則を満たす．

どの命令も \(A, H\) の2つで表現できる．

• \(1 = HA\)
• \(2 = HA^3\)
• \(V = HA^2\)
• \(B = A^2\)
• \(C = A^3\)
• \(X = A^3\)
• \(Y = A^2\)
• \(Z = A\)

また \(AH = HA^3\) であるから，任意の命令列は \(H^i A^j\) という形に変形できる． さらに明らかに \(H^2 = I, A^4 = I\) なので \(0 \le i \le 1, 0 \le j \le 3\) という8通りの命令列に変換できる．

あとはこの8通りの命令列に関して A と H での状態遷移を考えて，下図のようなオートマトンを構成して命令列を変換し，最後に実際に命令を実行すればいい．

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 
  5 typedef enum { A, H } op_type;
  6 
  7 struct automaton
  8 {
  9   int state;
 10   automaton() : state(0) {}
 11   automaton& operator<<(op_type o)
 12   {
 13     static const int tbl[8][2] = {
 14       {1, 4},
 15       {2, 7},
 16       {3, 6},
 17       {0, 5},
 18       {5, 0},
 19       {6, 3},
 20       {7, 2},
 21       {4, 1},
 22     };
 23     state = tbl[state][o];
 24     return *this;
 25   }
 26 
 27   void operator()(char mat[310][310], int& M, int& N) const
 28   {
 29     int s = state;
 30     if (s & 4) {
 31       for (int i = 0; i < M/2; i++) {
 32         for (int j = 0; j < N; j++) {
 33           swap(mat[i][j], mat[M-i-1][j]);
 34         }
 35       }
 36       s &= 3;
 37     }
 38     while (s-- > 0) {
 39       static char t[310][310];
 40       for (int i = 0; i < M; i++) {
 41         for (int j = 0; j < N; j++) {
 42           t[j][M-i-1] = mat[i][j];
 43           mat[i][j] = '\0';
 44         }
 45       }
 46       swap(M, N);
 47       for (int i = 0; i < M; i++) {
 48         for (int j = 0; j < N; j++) {
 49           mat[i][j] = t[i][j];
 50           t[i][j] = '\0';
 51         }
 52       }
 53     }
 54   }
 55 };
 56 
 57 int main()
 58 {
 59   int M, N;
 60   scanf("%d %d", &M, &N);
 61   static char mat[310][310];
 62   for (int i = 0; i < M; i++) {
 63     scanf("%s", mat[i]);
 64   }
 65 
 66   automaton a;
 67   int c;
 68   while ((c = getchar()) != EOF) {
 69     if (c == '\n') {
 70       continue;
 71     }
 72     switch (c) {
 73       case '1':
 74         a << H << A; break;
 75       case '2':
 76         a << H << A << A << A; break;
 77       case 'H':
 78         a << H; break;
 79       case 'V':
 80         a << H << A << A; break;
 81       case 'A':
 82       case 'Z':
 83         a << A; break;
 84       case 'B':
 85       case 'Y':
 86         a << A << A; break;
 87       case 'C':
 88       case 'X':
 89         a << A << A << A; break;
 90       default:
 91         throw "err";
 92     }
 93   }
 94   a(mat, M, N);
 95   printf("%d %d\n", M, N);
 96   for (int i = 0; i < M; i++) {
 97     puts(mat[i]);
 98   }
 99   return 0;
100 }