1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 105 6  7 typedef struct { 8     char s[5]; 9     char ch;10 } pattern_t;11 12 char line[2][MAXN];13 pattern_t pat[8];14 int t, n;15 16 int comp(const void *a, const void *b) {17     pattern_t *p = (pattern_t *)a;18     pattern_t *q = (pattern_t *)b;19     20     return strcmp(p->s, q->s);21 }22 23 int main() {24     int m;25     int i, j, k;26     int v;27     28 #ifndef ONLINE_JUDGE29     freopen("data.in", "r", stdin);30     freopen("data.out", "w", stdout);31 #endif32     33     scanf("%d", &t);34     while (t--) {35         scanf("%d", &m);36         for (i=0; i<8; ++i)37             scanf("%s %c", pat[i].s, &pat[i].ch);38         scanf("%s", line[0]+1);39         40         qsort(pat, 8, sizeof(pattern_t), comp);41         line[0][0] = line[1][0] = ‘0‘;42         k = 0;43         n = strlen(line[0]+1);44         while (m--) {45             line[k][n+1] = ‘\0‘;46             printf("%s\n", line[k]+1);47             line[k][n+1] = ‘0‘;48             j = !k;49             for (i=1; i<=n; ++i) {50                 v = ((line[k][i-1]-‘0‘)<<2) + ((line[k][i]-‘0‘)<<1) + (line[k][i+1]-‘0‘);51                 line[j][i] = pat[v].ch;52             }53             k = j;54         }55     }56     57     return 0;58 }