30 条题解
-
0
ZeroZerg LV 8 @ 2018-04-26 17:24:25
#1 Accepted 566ms 46.0 MiB
#2 Accepted 579ms 46.094 MiB
#3 Accepted 578ms 46.168 MiB
#4 Accepted 533ms 46.105 MiB
#5 Accepted 552ms 46.125 MiB
#6 Accepted 540ms 46.0 MiB
#7 Accepted 575ms 46.004 MiB
#8 Accepted 595ms 46.094 MiB
#9 Accepted 421ms 46.113 MiB
#10 Accepted 272ms 46.105 MiB按照现在的评测及配置，还是这样的通过速度，我猜当年的题目，暴力BFS是肯定会超时的。
一定需要进行减枝，最简单的减枝就是达成了目标后，后续的状态如果已经超过了这个步数，就直接跳过状态 耗时 内存占用
#1 Accepted 44ms 28.0 MiB
#2 Accepted 430ms 44.098 MiB
#3 Accepted 12ms 23.5 MiB
#4 Accepted 507ms 46.0 MiB
#5 Accepted 208ms 34.0 MiB
#6 Accepted 499ms 46.125 MiB
#7 Accepted 459ms 46.0 MiB
#8 Accepted 498ms 46.062 MiB
#9 Accepted 452ms 46.0 MiB
#10 Accepted 421ms 44.105 MiB事实证明加了这个减枝，只能好转，但并不治本。可能当时需要额外的减枝，估计需要一个估价值，选取更靠近答案的节点有限搜索
-
0
直接暴力BFS
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <tuple> using namespace std; constexpr int maxN = (int)1e6; constexpr int pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000}; int dist[6][maxN]; int src, dest; // 5 4 3 2 1 0 // -fr- -bk- // | | | | // X X X X X X // | | // d0 dp // pos=2 in this example int swap0(int val, int pos) { if (pos == 5) return -1; int d0 = val / pow10[5]; int dp = val / pow10[pos] % 10; return val + (dp - d0) * pow10[5] - (dp - d0) * pow10[pos]; } // 5 4 3 2 1 0 // -fr- -bk- // | | | | // X X X X X X // | | // dp d5 // pos=3 in this example int swap1(int val, int pos) { if (pos == 0) return -1; int d5 = val % 10; int dp = val / pow10[pos] % 10; return val + (d5 - dp) * pow10[pos] - (d5 - dp); } // 5 4 3 2 1 0 // -fr- --bk--- // | | | | // X X X X X X // | // d // pos=3 in this example int up(int val, int pos) { int d = val / pow10[pos] % 10; if (d == 9) return -1; return val + pow10[pos]; } int down(int val, int pos) { int d = val / pow10[pos] % 10; if (d == 0) return -1; return val - pow10[pos]; } int bfs() { if (src == dest) return 0; memset(dist, -1, sizeof(dist)); dist[5][src] = 0; queue<pair<int, int>> que; que.emplace(src, 5); int curV, curP; int nextV, nextP; while (!que.empty()) { tie(curV, curP) = que.front(); que.pop(); pair<int, int> nextS[] {{swap0(curV, curP), curP}, {swap1(curV, curP), curP}, {curV, curP - 1}, {curV, curP + 1}, {up(curV, curP), curP}, {down(curV, curP), curP}}; for (auto& pr: nextS) { tie(nextV, nextP) = pr; if (nextV != -1 && nextP >= 0 && nextP <= 5 && dist[nextP][nextV] == -1) { dist[nextP][nextV] = dist[curP][curV] + 1; que.emplace(nextV, nextP); if (nextV == dest) return dist[nextP][nextV]; } } } return -1; } int main() { scanf("%d%d", &src, &dest); printf("%d\n", bfs()); return 0; } -
0
const
maxl=6000000;
type
statetype=array[1..6] of longint;
nodetype=record
state:statetype;
point,step:longint;
end;
var
q:array[1..maxl] of nodetype;
app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9] of boolean;
st,start,closed:statetype;
i,tail,j,head,sp,pt,code:longint;
s:string;
function compare(var x,y:statetype;l:longint):boolean;
var
i:longint;
begin
compare:=true;
for i:=1 to l do
if x[i]<>y[i] then exit(false);
end;
beginread(s);
j:=pos(' ',s);
for i:=1 to j-1 do
val(s[i],start[i],code);
delete(s,1,j);
for i:=1 to length(s) do
val(s[i],closed[i],code);
j:=0;fillchar(app,sizeof(app),false);
head:=0;
tail:=1;
q[tail].state:=start;
q[tail].point:=1;
q[tail].step:=0;
while head<>tail do
begin
inc(head);
if head>maxl then head:=1;sp:=q[head].step;
pt:=q[head].point;
st:=q[head].state;if compare(st,closed,6) then
begin
writeln(sp);
exit;
end
else
begin
if (pt>1)and(not app[pt-1,st[1],st[2],st[3],st[4],st[5],st[6]])then
begin
inc(tail);
if tail>maxl then tail:=1;q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt-1;
app[pt-1,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;if (pt<6)and(not app[pt+1,st[1],st[2],st[3],st[4],st[5],st[6]]) then
begin
inc(tail);
if tail>maxl then tail:=1;
q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt+1;
app[pt+1,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;if st[pt]<9 then
begin
st[pt]:=st[pt]+1;
if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
then
begin
inc(tail);
if tail>maxl then tail:=1;
q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt;
app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;
st[pt]:=st[pt]-1;
end;
if st[pt]>0 then
begin
st[pt]:=st[pt]-1;
if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
then
begin
inc(tail);
if tail>maxl then tail:=1;
q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt;
app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;
st[pt]:=st[pt]+1;
end;i:=st[1];
j:=st[pt];st[1]:=j;
st[pt]:=i;
if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
then
begin
inc(tail);
if tail>maxl then tail:=1;
q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt;
app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;st[1]:=i;
st[pt]:=st[6];
st[6]:=j;
if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
then
begin
inc(tail);
if tail>maxl then tail:=1;
q[tail].state:=st;
q[tail].step:=sp+1;
q[tail].point:=pt;
app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
end;
end;
end;
end.
//可以用with do来优化；
之前自己挖了一个坑，就是st是全局数组，改变了状态没有复原；
可以写双向搜索，再加一个用位置+数值的估价函数来优化深搜（不过建议还是写成宽搜的）； -
0
#include <iostream> #include <map> #include <string> #include <queue> #include <cstring> using namespace std; struct state { int step; string s; }; string e; state st; map<string,int> my; queue<state> q; int bfs() { state t,tt; string ss; int i; q.push(st); my[st.s]=1; //Init while(!q.empty()) { t=q.front(); q.pop(); for(ss=t.s,i=0;i<6;i++) if(ss[i]!=e[i]) break; if(i==6) return t.step; ss=t.s; swap(ss[0],ss[ss[6]-'0']); if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } ss=t.s; swap(ss[5],ss[ss[6]-'0']); if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } ss=t.s; if(ss[ss[6]-'0']!='9'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']+=1; if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } ss=t.s; if(ss[ss[6]-'0']!='0'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']-=1; if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } ss=t.s; if(ss[6]-'0'!=0) { if(ss[6]!='5') { if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]-=1; } else ss[6]-=1; } if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } ss=t.s; if(ss[6]-'0'!=5) { if(ss[6]!='0') { if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]+=1; } else ss[6]+=1; } if(!my.count(ss)) { tt.s=ss; tt.step=t.step+1; q.push(tt); my[ss]=1; } } } int main() { cin>>st.s>>e; my.clear(); st.s+='0'; st.step=0; printf("%d",bfs()); }和楼下的时间比差远了
-
0
everforever LV 10 @ 2016-05-04 00:02:40
0 ms 576 KIB
......纯粹的人工剪枝......深刻体会到所谓暴力出奇迹......#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define MAXN 10000000
using namespace std;int now;
int minn=MAXN;
int ans=MAXN;
int use[2][6];
int poi=0;int tmp;
inline void s0(int x){int t=use[0][0];use[0][0]=use[0][x];use[0][x]=t;}
inline void s1(int x){int t=use[0][5];use[0][5]=use[0][x];use[0][x]=t;}bool check()
{
for(int i=0;i<6;i++)
if(use[0][i]!=use[1][i])
return false;
return true;
}int abs(int x)
{return x>0? x:-x;}int one[7];
int cnt[10];void dfs(int poi,int num,int yi)
{///*
if(check())
{ans=min(ans,num-1)/*,printf("%d: %d\n",poi,ans)*/;return ;}//*/
int t1,t2,t3,plus;
if(poi==5)
{
if(use[0][0]!=use[1][0])plus=abs(use[0][5]-use[1][0])+1+abs(use[0][0]-use[1][5]);
else plus=abs(use[1][5]-use[0][5]);
ans=min(ans,num+plus);
return ;
}if(poi==0)
{
// zhi chuan
dfs(poi+1,num+1,yi);
// huan chuan
s1(poi);
dfs(poi+1,num+2,yi);
s1(poi);
// bian chuan
t1=use[0][0];
plus=abs(use[0][0]-use[1][0]);
use[0][0]=use[1][0];
dfs(poi+1,num+plus+1,1);
use[0][0]=t1;
// huan bian chuan
t1=use[0][0];t2=use[0][5];
s1(poi);
plus=abs(use[0][0]-use[1][0])+1;
use[0][0]=use[1][0];
dfs(poi+1,num+plus+1,1);
use[0][0]=t1,use[0][5]=t2;
// bian huan chuan
t1=use[0][0],t2=use[0][5];
plus=abs(use[0][0]-use[1][5])+1;
use[0][0]=use[0][5],use[0][5]=use[1][5];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t1,use[0][5]=t2;
// bian huan bian chuan
t1=use[0][0],t2=use[0][5];
plus=abs(use[0][0]-use[1][5])+1+abs(use[0][5]-use[1][0]);
use[0][0]=use[1][0],use[0][5]=use[1][5];
dfs(poi+1,num+plus+1,1);
use[0][0]=t1,use[0][5]=t2;// bian huan bian huan chuan
if(use[0][5]!=use[1][5])
{
plus=abs(use[1][0]-use[0][0])+1+abs(use[1][5]-use[0][5])+1;
use[0][0]=use[1][0],use[0][5]=use[1][5];
dfs(poi+1,num+plus+1,1);
use[0][0]=t1,use[0][5]=t2;
}return ;
}t1=use[0][poi];
plus=abs(use[0][poi]-use[1][poi]);
use[0][poi]=use[1][poi];
dfs(poi+1,num+plus+1,yi);
use[0][poi]=t1;t2=use[0][0];
plus=abs(use[0][0]-use[1][poi])+1;
use[0][0]=use[0][poi],use[0][poi]=use[1][poi];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t2,use[0][poi]=t1;t2=use[0][0];
plus=abs(use[0][poi]-use[1][0])+1+abs(use[1][poi]-use[0][0]);
use[0][poi]=use[1][poi],use[0][0]=use[1][0];
dfs(poi+1,num+plus+1,1);
use[0][0]=t2;use[0][poi]=t1;t2=use[0][0],t3=use[0][5];
s0(poi),s1(poi);
plus=2+abs(use[0][poi]-use[1][poi]);
use[0][poi]=use[1][poi];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;s1(poi),s0(poi);
plus=2+abs(use[0][poi]-use[1][poi]);
use[0][poi]=use[1][poi];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;s0(poi),s1(poi);
plus=2+abs(use[0][poi]-use[1][poi])+abs(t1-use[1][0]);
use[0][poi]=use[1][poi];use[0][0]=use[1][0];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;s1(poi),s0(poi);
plus=2+abs(use[0][poi]-use[1][poi])+abs(t3-use[1][0]);
use[0][poi]=use[1][poi];use[0][0]=use[1][0];
dfs(poi+1,num+plus+1,yi);
use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;t2=use[0][5];
plus=abs(use[0][5]-use[1][poi])+1;
use[0][5]=use[0][poi],use[0][poi]=use[1][poi];
dfs(poi+1,num+plus+1,yi);
use[0][poi]=t1,use[0][5]=t2;t2=use[0][5];
plus=abs(use[0][poi]-use[1][5])+1+abs(use[1][poi]-use[0][5]);
use[0][poi]=use[1][poi],use[0][5]=use[1][5];
dfs(poi+1,num+plus+1,1);
use[0][5]=t2;use[0][poi]=t1;}
void into()
{
string s;
for(int i=0;i<2;i++)
{
cin>>s;
for(int j=0;j<6;j++)
{
use[i][j]=s[j]-'0';
if((cnt[use[i][j]]==0)&&(i==1))
one[++one[0]]=use[i][j],cnt[use[i][j]]++;
}
}
}int main()
{
into();
now=0;if(check())ans=0;
else dfs(0,0,0);printf("%d",ans);
//while(1);
return 0;
} -
0
qq872191552 LV 9 @ 2016-01-02 08:06:44
一开始还打了好多行...后来发现用一个数组s记下head里的序列，对它进行操作可以使代码简洁
-
0
不加任何剪枝的裸BFS也可以90分...不过大部分是卡着时限过的
-
0
只要一个剪枝就可以快速过：2~5位置上没达到目标状态不要用左右移
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
bool hash[10][10][10][10][10][10][7]; //序列为(a,b,c,d,e,f)且光标在g的状态是否出现过
struct bfs
{
char a[7];
char pos;
int dep;
}q[1000001]; //存下数字与光标位置int h=0,t=1;
char ait[7];
int p,d;
char s[7];bool check(char a,char b,char c,char d,char e,char f,int g)
{
return hash[a-'0'][b-'0'][c-'0'][d-'0'][e-'0'][f-'0'][g];
}bool yes(int k)
{
int i;
for(i=1;i<=6;i++)
if(q[k].a[i]!=ait[i]) return 0;
return 1;
}void change(char a,char b,char c,char d,char e,char f,int g)
{
hash[a-'0'][b-'0'][c-'0'][d-'0'][e-'0'][f-'0'][g]=1;
}void mcheck( )
{
int i;
if(!check(s[1],s[2],s[3],s[4],s[5],s[6],p))
{
change(s[1],s[2],s[3],s[4],s[5],s[6],p);
t=(t+1)%1000000;
for(i=1;i<=6;i++)
q[t].a[i]=s[i];
q[t].pos=p;
q[t].dep=d+1;
if(yes(t)) {printf("%d",d+1);exit(0);}
}
}int main( )
{int i,j,temp;
char c;for(i=1;i<=6;i++)
scanf("%c",&q[1].a[i]);scanf(" ");
for(i=1;i<=6;i++)
scanf("%c",&ait[i]);q[1].pos=1;
q[1].dep=0;//有一个点初始状态就是要求状态...
for(i=1;i<=6;i++)
if(ait[i]!=q[1].a[i]) goto trys;printf("0");return 0;
trys:;
while(h!=t)
{
h=(h+1)%1000000;
p=q[h].pos;
d=q[h].dep;
for(i=1;i<=6;i++)
s[i]=q[h].a[i];if(p!=1)
{
temp=s[p];s[p]=s[1];s[1]=temp;
mcheck( );
temp=s[p];s[p]=s[1];s[1]=temp;
}if(p!=6)
{
temp=s[p];s[p]=s[6];s[6]=temp;
mcheck( );
temp=s[p];s[p]=s[6];s[6]=temp;
}if(s[p]!='0')
{
s[p]--;
mcheck( );
s[p]++;
}if(s[p]!='9')
{
s[p]++;
mcheck( );
s[p]--;
}if(p==1 || p==6 || s[p]==ait[p]) //如果目前光标在2~5且当前位置上不符合要求，那么左移和右移不可能使其符合要求
{
if(p!=1)
{
p--;
mcheck( );
p++;
}if(p!=6)
{
p++;
mcheck( );
}
}
}return 0;
} -
0
测试数据 #0: Accepted, time = 93 ms, mem = 12172 KiB, score = 10
测试数据 #1: Accepted, time = 93 ms, mem = 12116 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 12016 KiB, score = 10
测试数据 #3: Accepted, time = 109 ms, mem = 12160 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 12156 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 12084 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 12156 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 12164 KiB, score = 10
测试数据 #8: Accepted, time = 124 ms, mem = 12192 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 12100 KiB, score = 10
作为一个傻逼。。。
人家100行代码我写了280+。。。。
算了贴个代码c++的
#include<bits/stdc++.h>
using namespace std;
class bitell
{
public:
int a[7];
// int w;
int light;
bitell();
bitell swap1();
bitell swap0();
bitell left();
bitell right();
bitell up();
bitell down();
bitell copyer();
};
void shuchu(bitell);
bitell::bitell()
{
light=1;
}
inline bitell bitell::copyer()
{
bitell p;
p.light=light;
for(int i=1;i<=6;i++)
p.a[i]=a[i];
return p;
}
inline bitell bitell::swap0()
{
int swapl;
bitell p;
p=copyer();
swapl=p.a[light];
p.a[light]=p.a[1];
p.a[1]=swapl;
return p;
}
inline bitell bitell::swap1()
{
bitell p;
int swapl;
p=copyer();
swapl=p.a[light];
p.a[light]=p.a[6];
p.a[6]=swapl;
return p;
}
inline bitell bitell::up()
{
bitell p;
p=copyer();
if(p.a[light]!=9)
p.a[light]++;
return p;
}
inline bitell bitell::down()
{
bitell p;
p=copyer();
if(p.a[light]!=0)
p.a[light]--;
return p;
}
inline bitell bitell::left()
{
bitell p;
p=copyer();
if(p.light!=1)
p.light--;
return p;
}
inline bitell bitell::right()
{
bitell p;
p=copyer();
if(p.light!=6)
p.light++;
return p;
}
queue<bitell> q;
queue<bitell> p;
bool vis[6000000];
bool vis2[6000000];
bitell start,fll;
int minl=-1;
int plength=1,qlength=1;
inline int change(bitell w)
{
int l=((w.a[1])*100000+(w.a[2])*10000+(w.a[3])*1000+(w.a[4])*100+(w.a[5])*10+(w.a[6]))+(w.light-1)*1000000;
return l;
}
bool operator ==(bitell a,bitell b)
{
for(int i=1;i<=6;i++)
if(a.a[i]!=b.a[i])
return false;
return true;
}
inline void put(bitell w)
{
if(vis[change(w)])
return;
if(w.a[w.light]!=0)
{
qlength++;
q.push(w.down());
}
if(w.light!=1&&((w.light==1||w.light==6)||(w.a[w.light]==fll.a[w.light])))
{
qlength++;
q.push(w.left());
}
if(w.light!=6&&((w.light==1||w.light==6)||(w.a[w.light]==fll.a[w.light])))
{
qlength++;
q.push(w.right());
}
if(w.a[w.light]!=w.a[1])
{
qlength++;
q.push(w.swap0());
}
if(w.a[w.light]!=9)
{
qlength++;
q.push(w.up());
}
if(w.a[w.light]!=w.a[6])
{
qlength++;
q.push(w.swap1());
}
return;
}
inline void put2(bitell w)
{
if(vis2[change(w)])
return;
if(w.a[w.light]!=0)
{
plength++;
p.push(w.down());
}
if(w.light!=1&&((w.light==1||w.light==6)||(w.a[w.light]==start.a[w.light])))
{
plength++;
p.push(w.left());
}
if(w.light!=6&&((w.light==1||w.light==6)||(w.a[w.light]==start.a[w.light])))
{
plength++;
p.push(w.right());
}
if(w.a[w.light]!=w.a[1])
{
plength++;
p.push(w.swap0());
}
if(w.a[w.light]!=9)
{
plength++;
p.push(w.up());
}
if(w.a[w.light]!=w.a[6])
{
plength++;
p.push(w.swap1());
}
return;
}bool find(int k)
{
int p1=qlength;
int oo;
while(p1!=0)
{
oo=change(q.front());
if(vis2[oo]||q.front()==fll)
{
minl=k;
return 1;
}
put(q.front());
vis[oo]=true;
q.pop();
p1--;
qlength--;
}
return 0;
}
bool find2(int k)
{
int p1=plength;
int oo;
while(p1!=0)
{
oo=change(p.front());
if(vis[oo]||p.front()==start)
{
minl=k;
return 1;
}
put2(p.front());
vis2[oo]=true;
p.pop();
plength--;
p1--;
}
return 0;
}
void clean()
{
while(!q.empty())
q.pop();
while(!p.empty())
p.pop();
return;
}
int main()
{
bool flag=1;
int kk=0;
minl=99999;
char pl[7];
for(int i=1;i<=6;i++)
cin>>pl[i];
for(int i=1;i<=6;i++)
start.a[i]=pl[i]-'0';
for(int i=1;i<=6;i++)
cin>>pl[i];
for(int i=1;i<=6;i++)
fll.a[i]=pl[i]-'0';
if(fll==start)
{
cout<<0<<endl;
return 0;
}
for(int i=1;i<=6;i++)
{
memset(vis,false,sizeof(vis));
memset(vis2,false,sizeof(vis2));
clean();
q.push(start);
p.push(fll);
find(0);
find2(0);
kk=1;
while(1)
{
if(qlength>plength)
{
if(find2(kk))
break;
}
else
if(find(kk))
break;
kk++;
if(qlength>plength)
{
if(find2(kk))
break;
}
else
if(find(kk))
break;
kk++;
if(kk>=minl)
break;
}
ww:
plength=qlength=1;
fll.light++;
}
cout<<minl<<endl;
return 0;
} -
0
whbjzzwjxq LV 8 @ 2014-07-02 19:12:44
program p1673;
var
f:array[0..720,1..6,1..2] of byte;
ans:array[0..720,1..6] of byte;
que:array[0..8000] of string;
que2:array[0..8000] of byte;
i,j:longint;
min:integer;
search:integer;
inp,aim,t:string;
procedure dfs;
var
p1,p2:integer;
work2:char;
link,tail:integer;
function hash(n:string):integer;
var
jc2:integer;
i,j,k:longint;
f:array[1..6] of byte;
len:integer;
begin
for i:=1 to 6 do begin f[i]:=i; end;
jc2:=120; len:=length(N);
hash:=0;
for i:=6 downto 2 do begin
val(n[len-i+1],j);
hash:=hash+(f[j]-1)*jc2;
for k:=j+1 to 6 do begin
f[k]:=f[k]-1; end;
jc2:=jc2 div (i-1);
end;
end;
procedure count(a,b:integer);
var
i,j,k,l:longint;
x:integer;
compare:string;
begin
x:=0;
compare:='';
k:=0;
for i:=1 to 6 do begin
val(que[link][i],j);
compare:=compare+t[j];
end;
for i:=1 to 6 do begin
val(aim[i],j);
val(compare[i],l);
x:=x+abs(j-l);end;
if compare[6]<>aim[6] then k:=6;
if compare[5]<>aim[5] then k:=k+4
else if compare[4]<>aim[4] then k:=k+3
else if compare[3]<>aim[3] then k:=k+2
else if compare[2]<>aim[2] then k:=k+1;
if f[a,b,2]=5 then f[a,b,2]:=10;
if f[a,b,2]=10 then ans[a,b]:=x+f[a,b,1]
else if (f[a,b,2]>5) then begin
if (k>5) then begin if (f[a,b,2]>=k) then ans[a,b]:=x+f[a,b,1];end
else if (f[a,b,2]-6>=k) then ans[a,b]:=x+f[a,b,1]; end
else if f[a,b,2]>=k then ans[a,b]:=x+f[a,b,1];
end;
begin
link:=0;
tail:=1;
f[0,1,1]:=0;
f[0,1,2]:=0;
que[0]:='123456';
que2[0]:=1;
while search>0 do begin
//swap 0
if que2[link]>1 then begin
p1:=hash(que[link]);
work2:=que[link][que2[link]];
que[link][que2[link]]:=que[link][1];
que[link][1]:=work2;
p2:=hash(que[link]);
if f[p2,que2[link],1]=200 then begin
f[p2,que2[link],2]:=f[p1,que2[link],2];
f[p2,que2[link],1]:=f[p1,que2[link],1]+1;
count(p2,que2[link]);
search:=search-1;
que2[tail]:=que2[link];
que[tail]:=que[link];
tail:=tail+1;
if tail>8000 then tail:=1;
end;
work2:=que[link][que2[link]];
que[link][que2[link]]:=que[link][1];
que[link][1]:=work2;
end;
//swap 6
if que2[link]<6 then begin
p1:=hash(que[link]);
work2:=que[link][que2[link]];
que[link][que2[link]]:=que[link][6];
que[link][6]:=work2;
p2:=hash(que[link]);
if f[p2,que2[link],1]=200 then begin
f[p2,que2[link],1]:=f[p1,que2[link],1]+1;
if f[p1,que2[link],2]<5 then begin
f[p2,que2[link],2]:=f[p1,que2[link],2]+6;
end else f[p2,que2[link],2]:=f[p1,que2[link],2];
count(p2,que2[link]);
search:=search-1;
que2[tail]:=que2[link];
que[tail]:=que[link];
tail:=tail+1;
if tail>8000 then tail:=1;
end;
work2:=que[link][que2[link]];
que[link][que2[link]]:=que[link][6];
que[link][6]:=work2;
end;
//left
if que2[link]>1 then begin
p1:=hash(que[link]);
que2[link]:=que2[link]-1;
if f[p1,que2[link],1]=200 then begin
f[p2,que2[link],2]:=f[p1,que2[link],2];
f[p1,que2[link],1]:=f[p1,que2[link]+1,1]+1;
search:=search-1;
count(p1,que2[link]);
que2[tail]:=que2[link];
que[tail]:=que[link];
tail:=tail+1;
if tail>8000 then tail:=1; end;
que2[link]:=que2[link]+1;
end;//right
if que2[link]<6 then begin
p1:=hash(que[link]);
que2[link]:=que2[link]+1;
if f[p1,que2[link],1]=200 then begin
f[p1,que2[link],1]:=f[p1,que2[link]-1,1]+1;
if (f[p1,que2[link]-1,2]<>10) then begin
if f[p1,que2[link]-1,2]>5 then begin if ((f[p1,que2[link]-1,2]-5)=que2[link]-1) then f[p1,que2[link],2]:=f[p1,que2[link]-1,2]+1; end
else if (f[p1,que2[link]-1,2]+2=que2[link]) then f[p1,que2[link],2]:=f[p1,que2[link]-1,2]+1;
end
else f[p1,que2[link],2]:=10;
search:=search-1;
count(p1,que2[link]);
que2[tail]:=que2[link];
que[tail]:=que[link];
tail:=tail+1; if tail>8000 then tail:=1; end;que2[link]:=que2[link]+1;
end;link:=link+1;
if link>8000 then search:=0;
end;
end; // all procedure
begin //main
read(inp);
fillchar(ans,sizeof(ans),100);
for i:=0 to 720 do
for j:=1 to 6 do begin
f[i,j,1]:=200;
f[i,j,2]:=0;end;
t:=copy(inp,1,6);
aim:=copy(inp,8,6);
min:=201;
search:=720*6;
if t=aim then min:=0
else dfs;
for i:=0 to 719 do
for j:=1 to 6 do begin
if ans[i,j]<min then min:=ans[i,j];
end;
writeln(min);
end.
看了大神的题解之后弄了一星期终于过了。。。 -
0
内存1000000*6的byte就OK。。然后弱菜依然TLE。。。。55555~
-
0
编译通过...
├ 测试数据 01：答案正确... (311ms, 84648KB)
├ 测试数据 02：答案正确... (690ms, 84648KB)
├ 测试数据 03：答案正确... (0ms, 84648KB)
├ 测试数据 04：答案正确... (831ms, 84648KB)
├ 测试数据 05：答案正确... (128ms, 84648KB)
├ 测试数据 06：答案正确... (815ms, 84648KB)
├ 测试数据 07：答案正确... (659ms, 84648KB)
├ 测试数据 08：答案正确... (784ms, 84648KB)
├ 测试数据 09：答案正确... (675ms, 84648KB)
├ 测试数据 10：答案正确... (522ms, 84648KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 5418ms / 84648KB
最朴素的宽搜..... 缩小内存用 byte -
0
sliverzero LV 8 @ 2010-03-29 19:33:31
内存挂了……我顶……看来这道题真的很不简单
-
0
TLE..
-
0
SecretAgent LV 10 @ 2009-10-22 22:25:39
现在很流行留名?
-
0
gnaggnoyil LV 10 @ 2009-10-21 21:49:33
看到zbwmqlw破了处来这里鄙视完zbwmqlw走人
ZeroZerg
LV 8
@ 2018-04-26 17:24:25
