[HDOJ5427]Cover

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5386
逆向思维，(初始状态没什么用。。)
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cmath>
  7 #include <queue>
  8 #include <map>
  9 #include <stack>
 10 #include <list>
 11 #include <vector>
 12 
 13 using namespace std;
 14 
 15 const int maxn = 111;
 16 const int maxm = 505;
 17 
 18 typedef struct Ord{
 19     int c, x, y;
 20 };
 21 
 22 int n, m;
 23 int color[maxn][maxn];
 24 int final[maxn][maxn];
 25 int vis[1000010];
 26 int ans[1000010];
 27 Ord ord[1000010];
 28 
 29 int main() {
 30     // freopen("in", "r", stdin);
 31     int T;
 32     char cmd[1];
 33     int x, y;
 34     scanf("%d", &T);
 35     while(T--) {
 36         memset(color, 0, sizeof(color));
 37         memset(final, 0, sizeof(final));
 38         memset(vis, 0, sizeof(vis));
 39         memset(ans, 0, sizeof(ans));
 40         scanf("%d %d", &n, &m);
 41         for(int i = 1; i <= n; i++) {
 42             for(int j = 1; j <= n; j++) {
 43                 scanf("%d", &color[i][j]);
 44             }
 45         }
 46         for(int i = 1; i <= n; i++) {
 47             for(int j = 1; j <= n; j++) {
 48                 scanf("%d", &final[i][j]);
 49             }
 50         }
 51         for(int i = 1; i <= m; i++) {
 52             scanf("%s %d %d", cmd, &x, &y);
 53             if(cmd[0] == 'H') {
 54                 ord[i].c = 0;
 55                 ord[i].x = x;
 56                 ord[i].y = y;
 57             }
 58             else if(cmd[0] == 'L') {
 59                 ord[i].c = 1;
 60                 ord[i].x = x;
 61                 ord[i].y = y;
 62             }
 63         }
 64         int cnt = 0;
 65         while(1) {
 66             for(int i = 1; i <= m; i++) {
 67                 if(vis[i]) {
 68                     continue;
 69                 }
 70                 if(ord[i].c == 0) {  //H 
 71                     int k = ord[i].x;
 72                     int j;
 73                     for(j = 1; j <= n; j++) {
 74                         if(final[k][j] != 0 && final[k][j] != ord[i].y) {
 75                             break;
 76                         }
 77                     }
 78                     if(j == n + 1) {
 79                         for(j = 1; j <= n; j++) {
 80                             final[k][j] = 0;
 81                         }
 82                         ans[++cnt] = i;
 83                         vis[i] = 1;
 84                     }
 85                     if(cnt == m) {
 86                        break;
 87                     }
 88                 }
 89                 else if(ord[i].c == 1) {  //L
 90                     int k = ord[i].x;
 91                     int j;
 92                     for(j = 1; j <= n; j++) {
 93                         if(final[j][k] != 0 && final[j][k] != ord[i].y) {
 94                             break;
 95                         }
 96                     }
 97                     if(j == n + 1) {
 98                         for(j = 1; j <= n; j++) {
 99                             final[j][k] = 0;
100                         }
101                         ans[++cnt] = i;
102                         vis[i] = 1;
103                     }
104                 }
105                 if(cnt == m) {
106                     break;
107                 }
108             }
109             if(cnt == m) {
110                 break;
111             }
112         }
113         for(int i = cnt; i > 0; i--) {
114             printf("%d ",ans[i]);
115         }
116         printf("
");
117     }
118     return 0;
119 }