UVALive 6755 - Swyper Keyboard-白红宇

UVALive 6755 - Swyper Keyboard

阅读量：2497 次

发布时间：2019-05-11

本文共 5312 字，大约阅读时间需要 17 分钟。

https://icpcarchive.ecs.baylor.edu/index.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 
   
    #include 
    #include 
     
      #include 
      
       using namespace std;const double eps = 0.000000001;typedef pair
       
         CC;#define  mp(a,b)  make_pair
        
         (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
         
          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){ //UR if(down && left) ret += dfsDL(rec); else if(left) ret += dfsL(rec); else if(down) ret += dfsD(rec); }else if(dir == L){ //R if(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){ //DR if(up && left) ret += dfsUL(rec); else if(left) ret += dfsL(rec); else if(up) ret += dfsU(rec); }else if(dir == U){//D if(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){ //DL if(up && right) ret += dfsUR(rec); else if(right) ret += dfsR(rec); else if(up) ret += dfsU(rec); }else if(dir == R){ //L if(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){//UL if(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 += tmp.erase(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
          
           ::iterator it = memo.begin(); it != memo.end(); it++)// cout<
           
            first.first<<" "<
            
             first.second<<" "<<(it->second)<
             
              >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<
              _<

by howard

转载地址：http://gbhrb.baihongyu.com/

你可能感兴趣的文章

docker原始镜像启动容器并创建Apache服务器实现反向代理