学步园

给你一个特殊的键盘，打字是通过滑行来打两个不同的字母的。现在给你这些打出的字母，找出打字时经过的其他字母。然后一些nc要求。

暴搞，或者自己枚举所有可能性。。。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8

using namespace std;

int cnt;
char key[104];
char road[20004];

/// * A B C D E *    00 01 02 03 04 05 06  ** 00 01 02 03 04 **
/// F G H I J K L    07 08 09 10 11 12 13  05 06 07 08 09 10 11
/// M N O P Q R S    14 15 16 17 18 19 20  12 13 14 15 16 17 18
/// T U V W X Y Z    21 22 23 24 25 26 27  19 20 21 22 23 24 25

int P[28][2] = {
        {2, 8}, {4, 8}, {6, 8}, {8, 8}, {10, 8}, {12, 8}, {14, 8},
        {2, 6}, {4, 6}, {6, 6}, {8, 6}, {10, 6}, {12, 6}, {14, 6},
        {2, 4}, {4, 4}, {6, 4}, {8, 4}, {10, 4}, {12, 4}, {14, 4},
        {2, 2}, {4, 2}, {6, 2}, {8, 2}, {10, 2}, {12, 2}, {14, 2},
};

int pos[26] = {
              1,  2,  3,  4,  5,
          7,  8,  9, 10, 11, 12, 13,
         14, 15, 16, 17, 18, 19, 20,
         21, 22, 23, 24, 25, 26, 27,
};

int ret[28] = {
         0,  0,  1,  2,  3,  4,  0,
         5,  6,  7,  8,  9, 10, 11,
        12, 13, 14, 15, 16, 17, 18,
        19, 20, 21, 22, 23, 24, 25,
};

int judge(int x1, int y1, int x2, int y2)
{
        return x1*y2 - x2*y1;
}

///给定起点位置和终点位置
void findroad(int first, int last)
{
        int dx = P[last][0] > P[first][0] ? 1 : -1;
        int dy = P[last][1] > P[first][1] ? 1 : -1;
        if(P[last][0] == P[first][0])
        {
                if(dy > 0) for(int i = first-7; i >= last; i -= 7) road[cnt++] = 'A' + ret[i];
                if(dy < 0) for(int i = first+7; i <= last; i += 7) road[cnt++] = 'A' + ret[i];
        }
        else if(P[last][1] == P[first][1])
        {
                if(dx > 0) for(int i = first+1; i <= last; i += 1) road[cnt++] = 'A' + ret[i];
                if(dx < 0) for(int i = first-1; i >= last; i -= 1) road[cnt++] = 'A' + ret[i];
        }
        else
        {
                int next = first;
                int sx = P[last][0] - P[first][0];
                int sy = P[last][1] - P[first][1];
                while((P[next][0] != P[last][0] || P[next][1] != P[last][1]) && next >= 0 && next <= 27)
                {
                        int tmpx = P[next][0] + dx;
                        int tmpy = P[next][1] + dy;
                        int tmpj = judge(sx, sy, tmpx - P[first][0], tmpy - P[first][1]);
                        if(dx < 0 && dy < 0)
                        {
                                if(tmpj < 0) next += 7;
                                if(tmpj > 0) next -= 1;
                                if(tmpj == 0) next += 6;
                        }
                        if(dx > 0 && dy < 0)
                        {
                                if(tmpj < 0) next += 1;
                                if(tmpj > 0) next += 7;
                                if(tmpj == 0) next += 8;
                        }
                        if(dx > 0 && dy > 0)
                        {
                                if(tmpj < 0) next -= 7;
                                if(tmpj > 0) next += 1;
                                if(tmpj == 0) next -= 6;
                        }
                        if(dx < 0 && dy > 0)
                        {
                                if(tmpj < 0) next -= 1;
                                if(tmpj > 0) next -= 7;
                                if(tmpj == 0) next -= 8;
                        }
                        if(next != 0 && next != 6) road[cnt++] = 'A' + ret[next];
                }
        }
}

int main()
{
        #ifdef BellWind
                freopen("12823.in", "r", stdin);
        #endif // BellWind

        int T;
        scanf("%d", &T);

        while(T--)
        {
                int n;
                scanf("%d %s", &n, key);
                cnt = 0;
                memset(road, 0, sizeof(road));
                int len = strlen(key);
                road[cnt++] = key[0];
                for(int l = 0; l+1 < len; l++) findroad(pos[key[l]-'A'], pos[key[l+1]-'A']);
                road[cnt] = '\0';
//                puts(road);
                bool flag = true;
                for(int t = 0; t < n; t++)
                {
                        char word[104];
                        scanf("%s", word);
                        if(flag)
                        {
                                int lenw = strlen(word);
                                int k, l;
                                for(l = 0, k = 0; l < cnt && k < lenw; l++) if(word[k] == road[l]) k++;
                                if(k == lenw)
                                {
                                        flag = false;
                                        printf("%s\n", word);
                                }
                        }
                }
                if(flag) printf("NO SOLUTION\n");
        }

        return 0;
}