hdu 5386 模拟

想明白以后会发现其实就是模拟...

因为每次只能给一整行或者一整列赋值，所以目标矩阵一开始一定有一行或者一列上数字都是相同的，找到对应的操作，把那一行或者那一列标记为访问过（即从原矩阵中删除）。然后新的矩阵也一定能找到一行或者一列数字都相同，再找到相应的操作，标记那一行或者那一列，依次类推，然后没有用到的操作随便找个顺序就好了。其实初始矩阵并没有什么用......

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int N = 101;
  7 const int M = 501;
  8 int mp1[N][N];
  9 int mp2[N][N];
 10 int goal[N][N];
 11 bool visit[N][N];
 12 bool used[M];
 13 int ans[M];
 14 int n, m, cnt;
 15 
 16 struct Node
 17 {
 18     char op[2];
 19     int x, y;
 20 } node[M];
 21 
 22 int checkRow( int row )
 23 {
 24     int j = 1;
 25     while ( j <= n && visit[row][j] ) j++;
 26     if ( j == n + 1 ) return -1;
 27     int num = goal[row][j];
 28     for ( int k = j + 1; k <= n; k++ )
 29     {
 30         if ( visit[row][k] ) continue;
 31         if ( num != goal[row][k] ) return -1;
 32     }
 33     return num;
 34 }
 35 
 36 int checkCol( int col )
 37 {
 38     int i = 1;
 39     while ( i <= n && visit[i][col] ) i++;
 40     if ( i == n + 1 ) return -1;
 41     int num = goal[i][col];
 42     for ( int k = i + 1; k <= n; k++ )
 43     {
 44         if ( visit[k][col] ) continue;
 45         if ( num != goal[k][col] ) return -1;
 46     }
 47     return num;
 48 }
 49 
 50 void solve()
 51 {
 52     memset( visit, 0, sizeof(visit) );
 53     memset( used, 0, sizeof(used) );
 54     cnt = 1;
 55     while ( 1 )
 56     {
 57         bool flag = false;
 58         for ( int row = 1; row <= n; row++ )
 59         {
 60             int tmp = checkRow(row);
 61             if ( tmp != -1 && mp1[row][tmp] != -1 )
 62             {
 63                 ans[cnt++] = mp1[row][tmp];
 64                 used[mp1[row][tmp]] = true;
 65                 for ( int k = 1; k <= n; k++ )
 66                 {
 67                     visit[row][k] = 1;
 68                 }
 69                 flag = true;
 70             }
 71         }
 72         for ( int col = 1; col <= n; col++ )
 73         {
 74             int tmp = checkCol(col);
 75             if ( tmp != -1 && mp2[col][tmp] != -1 )
 76             {
 77                 ans[cnt++] = mp2[col][tmp];
 78                 used[mp2[col][tmp]] = true;
 79                 for ( int k = 1; k <= n; k++ )
 80                 {
 81                     visit[k][col] = 1;
 82                 }
 83                 flag = true;
 84             }
 85         }
 86         if ( !flag ) break;
 87     }
 88     for ( int i = 1; i <= m; i++ )
 89     {
 90         if ( !used[i] )
 91         {
 92             ans[cnt++] = i;
 93         }
 94     }
 95     for ( int i = m; i > 1; i-- )
 96     {
 97         printf("%d ", ans[i]);
 98     }
 99     printf("%d
", ans[1]);
100 }
101 
102 int main()
103 {
104     int t;
105     scanf("%d", &t);
106     while ( t-- )
107     {
108         scanf("%d%d", &n, &m);
109         for ( int i = 1; i <= n; i++ )
110         {
111             for ( int j = 1; j <= n; j++ )
112             {
113                 scanf("%d", &goal[i][j]);
114             }
115         }
116         for ( int i = 1; i <= n; i++ )
117         {
118             for ( int j = 1; j <= n; j++ )
119             {
120                 scanf("%d", &goal[i][j]);
121             }
122         }
123         memset( mp1, -1, sizeof(mp1) );
124         memset( mp2, -1, sizeof(mp2) );
125         for ( int i = 1; i <= m; i++ )
126         {
127             scanf("%s %d %d", &node[i].op, &node[i].x, &node[i].y);
128             if ( node[i].op[0] == 'H' )
129             {
130                 mp1[node[i].x][node[i].y] = i;
131             }
132             else
133             {
134                 mp2[node[i].x][node[i].y] = i;
135             }
136         }
137         solve();
138     }
139     return 0;
140 }