HOJ 12823 Swyper Keyboard （模拟）

HOJ 12823 Swyper Keyboard （模拟）

给你一个特殊的键盘，打字是通过滑行来打两个不同的字母的。现在给你这些打出的字母，找出打字时经过的其他字母。然后一些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-8using 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 25int 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 BellWindfreopen("12823.in", "r", stdin);#endif // BellWindint 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] = '';
//                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("%sn", word);}}}if(flag) printf("NO SOLUTIONn");}return 0;
}