首页 > 代码库 > Vijos CoVH之再破难关(搜索+hash)
Vijos CoVH之再破难关(搜索+hash)
背景
在瞬间之下,明白所有真相
只要开始,就不会停止...
揭开唯一事实,外表是小孩,头脑却是大人
他的名字就叫...名侦探柯南！
描述
[CoVH07]
OIBH组织派出的黄金十二人+青铜五小强还没有到, 他们只能指望原先的机关能够阻拦住柯南的脚步.
柯南打开大门之后发现里面还有一个门, 门上还有一个神奇的锁(-,-)
这是一个4*4的锁, 上面有8个凸起的格子和8个被按下的格子
当且仅当两个格子有公共边时, 则称这两个格子是相邻的。
每次操作只能够交换相邻的两个格子
柯南看到了初始锁的状态 和目标锁的状态
同样组织只允许他用最少步数打开锁
格式
输入格式
第1到4行每行四个数字（1或者0），描述了初始锁状态
接着是一个空行
第6到9行每行四个数字，描述了最终锁状态
输出格式
输出文件只有一行，是一个整数n，表示最少的操作次数。
样例1
样例输入1
11110000111000101010010110100101Copy
样例输出1
4Copy
限制
全部1秒
提示
柯南成功突破了又一道门
他将继续向前进
而黄金十二人+青铜五小强又在哪里.......
来源
提供：*******@***牛
对他的无私贡献表示崇拜和感谢！@_@
成功拉低了1%的AC率
1 /* 2 bfs+数组判重 3 状态很少 只有2^16 4 直接用数组就好了 5 */ 6 #include<map> 7 #include<cstdio> 8 #include<iostream> 9 #define MAXN 40001010 11 using namespace std;12 13 struct node {14 int a[4][4];15 };16 node e[MAXN];17 18 int mp[4][4];19 20 int step[MAXN],head,tail;21 22 int x[4]= {0,1,0,-1};23 int y[4]= {1,0,-1,0};24 25 char s[10];26 27 bool flag,_HASH[1300000];28 29 map<node,int> m;30 31 inline bool pd(int xx,int yy) {32 if(xx<0||yy<0) return false;33 if(xx>=4||yy>=4) return false;// 啊啊mdzz 这里忘了‘=’ 害我错了18次 34 else return true;35 }36 37 inline bool check() {38 for(int i=0; i<4; i++)39 for(int j=0; j<4; j++)40 if(mp[i][j]!=e[tail].a[i][j]) return false;41 return true;42 }43 44 inline bool _hash() {45 int now=0;46 for(int i=0;i<4;i++)47 for(int j=0;j<4;j++) {48 now<<=1;49 now+=e[tail].a[i][j];50 }51 if(_HASH[now]) return false;52 _HASH[now]=true;53 return true; 54 }55 56 inline void search() {57 while(head<tail) {58 for(int xx=0; xx<4; xx++)59 for(int yy=0; yy<4; yy++) 60 for(int i=0; i<4; i++) {61 int _x=xx+x[i];62 int _y=yy+y[i];63 if(pd(_x,_y)) {64 for(int i=0; i<4; i++)65 for(int j=0; j<4; j++)66 e[tail].a[i][j]=e[head].a[i][j];67 step[tail]=step[head]+1;68 swap(e[tail].a[_x][_y],e[tail].a[xx][yy]);69 if(check()) {70 printf("%d\n",step[tail]);71 return;72 }73 if(_hash()) tail++;74 }75 }76 head++;77 }78 }79 80 int main() {81 for(int i=0; i<4; i++) {82 scanf("%s",s);83 for(int j=0; j<4; j++)84 mp[i][j]=s[j]-48;85 }86 for(int i=0; i<4; i++) {87 scanf("%s",s);88 for(int j=0; j<4; j++)89 e[0].a[i][j]=s[j]-48;90 }91 if(check()) {92 printf("0\n");93 return 0;94 }95 tail=1;96 search();97 return 0;98 }
Vijos CoVH之再破难关(搜索+hash)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。