UVALive 6755

UVALive 6755

.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4767&mosmsg=Submission+received+with+ID+1453512

模拟出所有对应字母二元组对应的字符串，保存到map里面。

难点是怎么计算，我写的比较麻烦，对于每一个方块，我用先计算直线与矩形哪条边相交，再DFS那个方向与它相邻的方块。此处有卡精度，比如我就在A Z ABHIJQRYZ这儿卡了一发，因为正确的解是A Z ABHIQRYZ，计算的时候加个eps。然后只要预处理出所有的，最后用的时候再查就可以了。

代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
using namespace std;
const double eps = 0.000000001;
typedef pair<char, char> CC;
#define  mp(a,b)  make_pair<char,char>(a,b)
#define U 1
#define UR 2
#define R 3
#define DR 4
#define D 5
#define DL 6
#define L 7
#define UL 8
#define dfsU(rec)  DFS(rect[pos[rec.y+1][rec.x]], U)
#define dfsUR(rec)  DFS(rect[pos[rec.y+1][rec.x+1]], UR)
#define dfsR(rec)  DFS(rect[pos[rec.y][rec.x+1]], R)
#define dfsDR(rec)  DFS(rect[pos[rec.y-1][rec.x+1]], DR)
#define dfsD(rec)  DFS(rect[pos[rec.y-1][rec.x]], D)
#define dfsDL(rec)  DFS(rect[pos[rec.y-1][rec.x-1]], DL)
#define dfsL(rec)  DFS(rect[pos[rec.y][rec.x-1]], L)
#define dfsUL(rec)  DFS(rect[pos[rec.y+1][rec.x-1]], UL)
map<CC, string>memo;
double a, b;
int special;struct Rect{int x, y;char ch;double u,d,l,r;
}rect[30];
int pos[5][8];int hor(double x1, double x2, double y){//与水平边相交if(special){return x1 <= a+eps && a-eps <= x2;}else{double y1 = a*x1 + b;double y2 = a*x2 + b;return (y1 <= y+eps && y-eps <= y2) || (y1 >= y-eps && y+eps >= y2);}
}int ver(double y1, double y2, double x){//与垂直边相交if(special){return 0;}else{if(a == 0){return (y1 <= b+eps && b-eps <= y2) || (y1 >= b-eps && b+eps >= y2);}else{double x1 = (y1 - b) / a;double x2 = (y2 - b) / a;return (x1 <= x+eps && x-eps <= x2) || (x1 >= x-eps && x+eps >= x2);}}
}
Rect S, E;void calab(){double x1 = S.x, x2 = E.x;double y1 = S.y, y2 = E.y;if(x1 == x2){special = 1;a = x1;return ;}else{special = 0;a = (y2-y1)/(x2-x1);b = y1 - a*x1;}
}int caldir(){if(S.y < E.y && S.x == E.x) return U;if(S.y < E.y && S.x < E.x) return UR;if(S.y == E.y && S.x < E.x) return R;if(S.y > E.y && S.x < E.x) return DR;if(S.y > E.y && S.x == E.x) return D;if(S.y > E.y && S.x > E.x) return DL;if(S.y == E.y && S.x > E.x) return L;if(S.y < E.y && S.x > E.x) return UL;return 0;
}string DFS(Rect rec, int dir){//直线从上一个方块的哪个方向进来string ret = "";if(rec.ch != '#')ret += rec.ch;if(rec.ch == E.ch) {return ret;}int up = hor(rec.l, rec.r, rec.u);int right = ver(rec.u, rec.d, rec.r);int down = hor(rec.l, rec.r, rec.d);int left = ver(rec.u, rec.d, rec.l);if(dir == D){if(down && left) ret += dfsDL(rec);else if(down && right) ret += dfsDR(rec);else if(left) ret += dfsL(rec);else if(right) ret += dfsR(rec);else if(down) ret += dfsD(rec);}else if(dir == DL){ //URif(down && left) ret += dfsDL(rec);else if(left) ret += dfsL(rec);else if(down) ret += dfsD(rec);}else if(dir == L){ //Rif(up && left) ret += dfsUL(rec);else if(down && left) ret += dfsDL(rec);else if(up) ret += dfsU(rec);else if(left) ret += dfsL(rec);else if(down) ret += dfsD(rec);}else if(dir == UL){ //DRif(up && left) ret += dfsUL(rec);else if(left) ret += dfsL(rec);else if(up) ret += dfsU(rec);}else if(dir == U){//Dif(up && left) ret += dfsUL(rec);else if(up && right) ret += dfsUR(rec);else if(left) ret += dfsL(rec);else if(right) ret += dfsR(rec);else if(up) ret += dfsU(rec);}else if(dir == UR){ //DLif(up && right) ret += dfsUR(rec);else if(right) ret += dfsR(rec);else if(up) ret += dfsU(rec);}else if(dir == R){ //Lif(up && right) ret += dfsUR(rec);else if(down && right) ret += dfsDR(rec);else if(up) ret += dfsU(rec);else if(right) ret += dfsR(rec);else if(down) ret += dfsD(rec);}else if(dir == DR){//ULif(down && right) ret += dfsDR(rec);else if(right) ret += dfsR(rec);else if(down) ret += dfsD(rec);}return ret;
}string calstr(string str){string ret = "";int len = str.length();ret = str[0];for(int i = 1; i < len; i++){CC cc;cc.first = str[i-1];cc.second = str[i];string tmp = memo[cc];ret += ase(0,1);}return ret;
}int main(){
//    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);int m = 0;/** 读入方块坐标 **/for(int x = 2, y = 4; x <= 6; x++){rect[m].x = x;rect[m].y = y;m++;}for(int y = 3; y >= 1; y--){for(int x = 1; x <= 7; x++){rect[m].x = x;rect[m].y = y;m++;}}rect[m].x = 1;rect[m].y = 4;m++;rect[m].x = 7;rect[m].y = 4;m++;memset(pos, 0, sizeof 0);for(int i = 0; i < m; i++){pos[rect[i].y][rect[i].x] = i;rect[i].ch = 'A'+i;rect[i].u = 1.0*rect[i].y+0.5;rect[i].r = 1.0*rect[i].x+0.5;rect[i].d = 1.0*rect[i].y-0.5;rect[i].l = 1.0*rect[i].x-0.5;}rect[26].ch = '#';rect[27].ch = '#';for(int y = 4; y >= 1; y--)for(int x = 1; x <= 7; x++){S = rect[pos[y][x]];if(S.ch == '#') continue;for(int yy = 4; yy >= 1; yy--)for(int xx = 1; xx <= 7; xx++){E = rect[pos[yy][xx]];if(E.ch == '#') continue;CC cc;cc.first = S.ch;cc.second = E.ch;calab();memo[cc] = DFS(S, caldir());}}
//    for(map<CC,string>::iterator it = memo.begin(); it != d(); it++)
//        cout<<it->first.first<<" "<<it->first.second<<" "<<(it->second)<<endl;/*** Solve ***/int T;scanf("%d", &T);while(T--){int m;string sub, str;cin>>m>>str;int ok  = 0;int len;str = calstr(str);len = str.length();while(m--){cin>>sub;int sublen = sub.length();if(ok) continue;for(int i = 0, j = 0; i < len && j < sublen; i++){while(str[i] == sub[j] && i < len && j < sublen) i++, j++;if(j == sublen) ok = 1;}if(ok) cout<<sub<<endl;}if(!ok) cout<<"NO SOLUTION"<<endl;}return 0;
}

by howard