BZOJ 1054 移动玩具
Description
某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使得自己的名字能够扩充得很长。现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。
Input
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行,每行两个字母,表示W可以用这两个字母替代。接下来I行,每行两个字母,表示I可以用这两个字母替代。接下来N行,每行两个字母,表示N可以用这两个字母替代。接下来G行,每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
Output
一行字符串,该名字可能由哪些字母变形而得到。(按照WING的顺序输出)如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”
Sample Input
II
WW
WW
IG
IIII
Sample Output
HINT
W可以变成II所以IIII可以缩成WW IN均能变成WW所以WW又可以缩成I或者N 所以最终答案应该按照“WING”的顺序输出IN
[数据范围]
100%数据满足Len<=200,W、I、N、G<=16
Source
广度优先搜索大水题不解释。
1 #include<algorithm> 2 #include<queue> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 7 int st,aim,xx[4] = {0,1,0,-1},yy[4] = {1,0,-1,0}; bool exist[1<<20]; 8 9 inline pair<int,int> loc(int id) 10 { 11 int rx = (id+3)/4,ry = id-rx*4+4; 12 return make_pair(rx,ry); 13 } 14 15 inline int ord(int x,int y) { return (x-1)*4+y; } 16 17 inline bool okay(int x,int y) 18 { 19 if (x < 1) return false; 20 if (x > 4) return false; 21 if (y < 1) return false; 22 if (y > 4) return false; 23 return true; 24 } 25 26 inline void work() 27 { 28 queue < pair <int,int> > team; 29 team.push(make_pair(st,0)); exist[st] = true; 30 pair <int,int> now,temp; int sta; 31 while (!team.empty()) 32 { 33 now = team.front(); team.pop(); 34 if (now.first == aim) 35 { 36 printf("%d",now.second); 37 return; 38 } 39 for (int i = 1;i <= 16;++i) 40 { 41 if (now.first & (1<<(i-1))) 42 { 43 temp = loc(i); 44 int nx = temp.first,ny = temp.second; 45 for (int j = 0;j < 4;++j) 46 { 47 int px = nx+xx[j],py = ny+yy[j]; 48 if (okay(px,py)&&!(now.first&(1<<(ord(px,py)-1)))) 49 { 50 sta = now.first; sta ^= 1<<(i-1); sta |= (1<<(ord(px,py)-1)); 51 if (!exist[sta]) 52 team.push(make_pair(sta,now.second+1)),exist[sta] = true; 53 } 54 } 55 } 56 } 57 } 58 } 59 60 inline int get() 61 { 62 int ret = 0,a; 63 for (int i = 0;i < 4;++i) scanf("%1d",&a),ret |= a<<i; 64 return ret; 65 } 66 67 int main() 68 { 69 freopen("1054.in","r",stdin); 70 freopen("1054.out","w",stdout); 71 int a; 72 for (int i = 1;i <= 4;++i) 73 { 74 a = get(); 75 st |= a << ((i-1)*4); 76 } 77 for (int i = 1;i <= 4;++i) 78 { 79 a = get(); 80 aim |= a << ((i-1)*4); 81 } 82 work(); 83 return 0; 84 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。