操练士兵
来源:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1433
如图1，由8个方格构成的训练场，间隔为虚线的表示两方格相通，五个士兵编号分别为1……5，初始时，士兵被随机地排列在第二行的5个格子中。士兵可以越过虚线进入相邻的没有被其他士兵占据的格子中，每移动一格算一步。
编程：给定5个士兵的初始位置（如图1），计算出将士兵排列为目标状态（如图2）时最少的步数。
输入：给定5个士兵的初始位置。
输出：最优步数，若无解输出-1。
样例读入：
45678
41638
对应的输出为：
2
代码
如果不考虑士兵的顺序的话。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<iostream> using namespace std; struct data{ bool a[9]; int step; }d[1000]; int t=0,w=1; int ans; string str1,str2; bool flag=0,hash[1000]; bool temp[9]; int xx[4]={-4,4,-1,1}; void ini() { for(int i=1;i<=8;i++)d[w].a[i]=d[t].a[i]; } int Hash(bool a[]) { int s=0; for(int i=1;i<=8;i++) s+=a[i]<<(i-1); return s; } void bfs() { for(int i=0;i<5;i++)d[t].a[str1[i]-'0']=1; hash[Hash(d[t].a)]=1; if(Hash(d[t].a)==ans){cout<<0;flag=1;return;} ini(); while(t<w) { for(int i=1;i<=8;i++) { for(int j=0;j<4;j++) { ini(); if(d[w].a[i]&&!d[w].a[i+xx[j]]&&i+xx[j]>=1&&i+xx[j]<=8) { if(i==4&&(j==1||j==2))continue; if(i==8&&j==0)continue; if(i==3&&j==3)continue; swap(d[w].a[i],d[w].a[i+xx[j]]); d[w].step=d[t].step+1; if(Hash(d[w].a)==ans) { flag=1; cout<<d[w].step; return; } if(!hash[Hash(d[w].a)]) { hash[Hash(d[w].a)]=1; w++; } } } } t++; } } int main() { cin>>str1>>str2; for(int i=0;i<5;i++)temp[str2[i]-'0']=1; ans=Hash(temp); bfs(); if(!flag)cout<<-1; return 0; } |
考虑顺序的话…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> using namespace std; struct data{ int a[6]; int step; }d[90000]; int t=0,w=1; int ans; string str1; bool flag=0,hash[90000]; int xx[4]={-4,4,-1,1}; void ini() { for(int i=1;i<=5;i++)d[w].a[i]=d[t].a[i]; } int Hash(int a[]) { int k=1,s=0; for(int i=5;i>=1;i--) { s+=a[i]*k; k*=10; } return s; } bool pd(int x) { if(x<1||x>8)return 0; for(int i=1;i<=5;i++) if(d[t].a[i]==x)return 0; return 1; } void bfs() { int x; for(int i=0;i<5;i++)d[0].a[i+1]=str1[i]-'0'; hash[Hash(d[0].a)]=1; if(Hash(d[0].a)==ans){cout<<0;flag=1;return;} while(t<w) { for(int i=1;i<=5;i++) { for(int j=0;j<4;j++) { ini(); if(d[w].a[i]==4&&(j==1||j==2))continue; if(d[w].a[i]==8&&j==0)continue; if(d[w].a[i]==3&&j==3)continue; x=d[w].a[i]+xx[j]; if(pd(x)) { d[w].a[i]=x; d[w].step=d[t].step+1; if(Hash(d[w].a)==ans){ flag=1; cout<<d[w].step; return; } if(!hash[Hash(d[w].a)]) { hash[Hash(d[w].a)]=1; w++; } } } } t++; } } int main() { cin>>str1>>ans; bfs(); if(!flag)cout<<-1; return 0; } |
Subscribe
计数器 9788185
OI 课件=>
OI 课件=>