# 30 条题解

• @ 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

事实证明加了这个减枝，只能好转，但并不治本。可能当时需要额外的减枝，估计需要一个估价值，选取更靠近答案的节点有限搜索

• @ 2018-02-04 22:03:31

直接暴力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;
}
``````
• @ 2016-09-29 21:45:03

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;
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;
begin

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);
tail:=1;
q[tail].state:=start;
q[tail].point:=1;
q[tail].step:=0;
begin

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是全局数组，改变了状态没有复原；
可以写双向搜索，再加一个用位置+数值的估价函数来优化深搜（不过建议还是写成宽搜的）；

• @ 2016-08-14 17:41:30
``````#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());
}
``````

和楼下的时间比差远了

• @ 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;
}

• @ 2016-01-02 08:06:44

• @ 2016-01-02 08:03:34

不加任何剪枝的裸BFS也可以90分...不过大部分是卡着时限过的

• @ 2016-01-02 08:02:20

只要一个剪枝就可以快速过：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;
}

• @ 2015-12-09 17:40:43

测试数据 #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;
}

• @ 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;
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
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
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
if f[p2,que2[link],1]=200 then begin
search:=search-1;
tail:=tail+1;
if tail>8000 then tail:=1;
end;
end;
//swap 6
if que2[link]<6 then begin
if f[p2,que2[link],1]=200 then begin
if f[p1,que2[link],2]<5 then begin
search:=search-1;
tail:=tail+1;
if tail>8000 then tail:=1;
end;
end;
//left
if que2[link]>1 then begin
if f[p1,que2[link],1]=200 then begin
search:=search-1;
tail:=tail+1;
if tail>8000 then tail:=1; end;

end;

//right
if que2[link]<6 then begin
if f[p1,que2[link],1]=200 then begin
if (f[p1,que2[link]-1,2]<>10) then begin

end
search:=search-1;

end;

if link>8000 then search:=0;

end;
end; // all procedure
begin //main
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.
看了大神的题解之后弄了一星期终于过了。。。

• @ 2014-06-21 12:57:54

内存1000000*6的byte就OK。。然后弱菜依然TLE。。。。55555~

• @ 2012-09-06 18:34:57

编译通过...

├ 测试数据 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

• @ 2010-03-29 19:33:31

内存挂了……我顶……看来这道题真的很不简单

• @ 2009-11-02 08:37:57

1秒..........................

我去改改原来的程序.............

• @ 2009-10-30 14:22:03

额，时限这么短，看来单纯的宽搜是不行了。难道是双向宽搜或A＊？

膜拜过了的神牛们！

• @ 2009-10-24 12:15:44

555..TLE and MLE

• @ 2009-10-23 17:57:52

TLE..

• @ 2009-10-22 22:25:39

现在很流行留名?

• @ 2009-10-22 11:39:19

当年的竞赛不是时限到了好几秒吗...本人小菜...时限短了过不了...

• @ 2009-10-21 21:49:33

看到zbwmqlw破了处来这里鄙视完zbwmqlw走人

ID
1673

8

580

89

15%

3