129 条题解
-
1
^ambition LV 8 @ 6 年前
3s左右，代码应该容易看懂
-
1
算法
bfs
康托展开
数据结构
队列
技巧
从合法队形出发(允许我将最后他们要调到的队形称为合法队形)理由
如果从非合法队形出发bfs，那么每个队形都要搜索。搜个两三个牛一点的搜个七八个大概能行。但题目是每个测试文件50个队形。虽然每次搜索不是一定要搜索到所有的队形，但基本上接近。而从合法队形出发，则只需要搜索一次，虽然是要搜出所有的队形。但1和50大家知道怎么取舍。
如果是从非合法队形出发，那么你还要判断是否达到合法队形。这个时候你时间还需要再乘以一个数。即使你预先把正确答案的康托值算出，并且从小到大，然后逐一比较或使用了log n（n=8）的二分法查找，看是否达到。但还是乘了一个数。虽然不大，但这个……（经本人亲自实验，log n的二分在n=8的与逐一比较是一样一样的，甚至更慢） so，毫无疑问应到从合法队形出发
基本流程
初始化 base
8个合法队形入队（先用小学数学找出一个合法队形，别说你不会，然后对称呀，旋转变化，就可以得到8个，这个直接通过大脑更划算，用程序吃力不讨好）
bfs搜索，把解保存到f1中
读入，求康托值，输出对应的解
注意
限时是5秒，不是1秒
我就是没弄清这一点，使劲优化都是2.3s左右
然后在哪里使劲的优化优化呀，好悲剧呀
最后报着评测机可能比我的机子快3倍的决心试了一下，该死的忘记去掉一点本地的东西，然后无情的runtime error
再提交惊奇的发现红色的AC，基本都是2200多毫秒，就是大概2.2s多一点。不知是我家的机子快还是评测机慢？
然后仔细一看题目，发现限时5s。
顿时想死的心都有了，优化了这么久，这么久。竟然都是……这道题做法很多，可以正向搜索，倒序搜索，双向宽搜。
但由于打表程序（如下）告诉我们出口有8个，因此最方便的还是顺序搜索。虽然后两者更快。这是打印出的出口以及对应的康拓展开的值
-
1
yuyilahanbao LV 10 @ 11 年前
算法
- bfs
- 康托展开
数据结构
- 队列
技巧
- 从合法队形出发(允许我将最后他们要调到的队形称为合法队形)理由
- 如果从非合法队形出发bfs，那么每个队形都要搜索。搜个两三个牛一点的搜个七八个大概能行。但题目是每个测试文件50个队形。虽然每次搜索不是一定要搜索到所有的队形，但基本上接近。而从合法队形出发，则只需要搜索一次，虽然是要搜出所有的队形。但1和50大家知道怎么取舍。
- 如果是从非合法队形出发，那么你还要判断是否达到合法队形。这个时候你时间还需要再乘以一个数。即使你预先把正确答案的康托值算出，并且从小到大，然后逐一比较或使用了log n（n=8）的二分法查找，看是否达到。但还是乘了一个数。虽然不大，但这个……（经本人亲自实验，log n的二分在n=8的与逐一比较是一样一样的，甚至更慢） so，毫无疑问应到从合法队形出发
基本流程
初始化 base
8个合法队形入队（先用小学数学找出一个合法队形，别说你不会，然后对称呀，旋转变化，就可以得到8个，这个直接通过大脑更划算，用程序吃力不讨好）
bfs搜索，把解保存到f1中
读入，求康托值，输出对应的解注意
限时是5秒，不是1秒
我就是没弄清这一点，使劲优化都是2.3s左右
然后在哪里使劲的优化优化呀，好悲剧呀
最后报着评测机可能比我的机子快3倍的决心试了一下，该死的忘记去掉一点本地的东西，然后无情的runtime error
再提交惊奇的发现红色的AC，基本都是2200多毫秒，就是大概2.2s多一点。不知是我家的机子快还是评测机慢？
然后仔细一看题目，发现限时5s。
顿时想死的心都有了，优化了这么久，这么久。竟然都是……
code：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 362880
typedef char str[10];str queue[N+3];
int value[N+3];
int rear,front;int ta[] = {1,1,2,6,24,120,720,5040,40320};
int go[] = {-1,1,3,-3};char tmps[200] ="276951438294753618438951276492357816618753294672159834816357492834159672";
int f1[N+3];
int main()
{
int i,j,k;
char s[10];
void base();
void init(char *s);
int kangtuo(char *s);
void bfs();base(); bfs();
s[9] = 0;
for (i = 0;i < 50;i++) {
init(s);
printf("%d\n",f1[kangtuo(s)]);
}
return 0;
}int kangtuo(char *s)
{
char static used[9];
int static i,j,k,v;
memset(used,1,sizeof(used));
for (v = k = 0;k < 8;k++,s++) {
for (j = i = 0;i < *s-'1';i++)
j += used[i];
v += j*ta[8-k]; //ta[9-k-1]
used[*s-'1'] = 0;
}
return v;
}void init(char *s)
{
int i,k;
for (i = 0;i < 9;i++) {
scanf("%d",&k);
*(s+i) = k+'0';
}
}void base()
{
int i,f;
memset(queue,0,sizeof(queue));
memset(value,0,sizeof(value));
for (i = 0;i < N;i++)
f1[i] = -1;
rear = front = 0;
for (i = 0;i < 8;i++) {
strncpy(queue[rear],tmps+i*9,9);
f = kangtuo(queue[rear]);
f1[f] = 0;
rear++;
}
}int can_go(int a,int b)
{
switch (b) {
case -1:return (a%3 > 0);
case +1:return (a%3 < 2);
case -3:return (a/3 > 0);
case +3:return (a/3 < 2);
}
return 0;
}void swap_one(int a,int b)
{
strcpy(queue[rear],queue[front]);
queue[rear][b] = queue[front][a]; queue[rear][a] = queue[front][b];
}void bfs()
{
int i,j,f;
while (front < rear) {
if (rear > N-1)
return;
for (i = 0;i < 9;i++) {
//expand();
for (j = 0;j < 4;j++) {
if (can_go(i,go[j])) {
swap_one(i,i+go[j]);
f = kangtuo(queue[rear]);
if (f1[f] == -1) {
f1[f] = value[rear++] = value[front]+1;
}
}
}
}
front++;
}
return;
} -
0
larryzhong LV 9 @ 7 年前
-
0
测试数据 #0: Accepted, time = 2171 ms, mem = 47524 KiB, score = 10
测试数据 #1: Accepted, time = 1968 ms, mem = 47528 KiB, score = 10
测试数据 #2: Accepted, time = 1921 ms, mem = 47528 KiB, score = 10
测试数据 #3: Accepted, time = 2171 ms, mem = 47528 KiB, score = 10
测试数据 #4: Accepted, time = 1921 ms, mem = 47524 KiB, score = 10
测试数据 #5: Accepted, time = 2156 ms, mem = 47528 KiB, score = 10
测试数据 #6: Accepted, time = 2203 ms, mem = 47528 KiB, score = 10
测试数据 #7: Accepted, time = 2312 ms, mem = 47524 KiB, score = 10
测试数据 #8: Accepted, time = 1968 ms, mem = 47528 KiB, score = 10
测试数据 #9: Accepted, time = 1734 ms, mem = 47524 KiB, score = 10
Accepted, time = 20525 ms, mem = 47528 KiB, score = 100纯暴力bfs+hash。。。想研究一下那些几百毫秒dalao的方法。。
代码
```c++
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define maxn 30
#define INF 66666666
#define min(a,b) (a)>(b)?(b):(a)
#define Mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef int State[9];
const int MAXSIZE = 1000000;
const int MAXHASHSIZE = 1000003;
int Head[MAXHASHSIZE], Next[MAXHASHSIZE];
State st[MAXSIZE], goal;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int dist[MAXSIZE];void init(){
Mem(Head, 0);
}
int Hash(State &s){
int v = 0;
for (int i = 0; i < 9; i += 1)
v = v * 10 + s[i];
return v % MAXHASHSIZE;
}
int try_to_insert(int s){
int h = Hash(st[s]);
int u = Head[h];
while (u)
{
if (memcmp(st[u], st[s], sizeof(st[u])) == 0)
return 0;
u = Next[u];
}
Next[s] = Head[h];
Head[h] = s;
return 1;
}
//0 1 2
//3 4 5
//6 7 8
int judge(const State& s){
if (s[0] + s[1] + s[2] != 15)
return 0;
if (s[3] + s[4] + s[5] != 15)
return 0;
if (s[6] + s[7] + s[8] != 15)
return 0;
if (s[0] + s[3] + s[6] != 15)
return 0;
if (s[1] + s[4] + s[7] != 15)
return 0;
if (s[2] + s[5] + s[8] != 15)
return 0;
if (s[0] + s[4] + s[8] != 15)
return 0;
if (s[2] + s[4] + s[6] != 15)
return 0;
return 1;
}
int bfs(){
int front = 1, rear = 2;
init();
while (front < rear){
State & s = st[front];
if (judge(s)) return front;
for (int i = 0; i < 9; i += 1){
int x = i / 3, y = i % 3;
for (int j = 0; j < 4; j += 1){
State & t = st[rear];
memcpy(&t, &s, sizeof(s));
int nx = x + dx[j], ny = y + dy[j], nz = nx * 3 + ny;
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
{
t[nz] = s[i]; t[i] = s[nz];
dist[rear] = dist[front] + 1;
if (try_to_insert(rear))
rear += 1;
}
}
}
front += 1;
}
return 0;
}
int main(){
vector<int> anses;
for (int i = 0; i < 50; i += 1){
Mem(st, 0);
Mem(Next, 0);
Mem(dist, 0);
for (int j = 0; j < 9; j += 1)
scanf("%d", &st[1][j]);
int ans = bfs();
if (ans > 0) anses.push_back(dist[ans]);
else anses.push_back(-1);
}
for (int i = 0; i < anses.size(); i += 1)
printf("%d\n", anses[i]);
return 0;
}
``` -
0
暴力宽搜
label 10;
type rec=record q:array [1..9] of integer;bu:longint; end;
var a:array [1..9] of integer;
f:array [1..9,1..9,1..9,1..9,1..9,1..9,1..9,1..9] of boolean;
b:array [1..1000000] of rec;
i,j,k,l,n,m,t,w:longint;
procedure swap(r,t:longint);
var w:integer;
begin
w:=a[r];a[r]:=a[t];a[t]:=w;
end;
function check:boolean;
begin
check:=true;
if (a[1]+a[2]+a[3]<>15) then exit(false);
if (a[4]+a[5]+a[6]<>15) then exit(false);
if (a[7]+a[8]+a[9]<>15) then exit(false);
if (a[1]+a[4]+a[7]<>15) then exit(false);
if (a[2]+a[5]+a[8]<>15) then exit(false);
if (a[3]+a[6]+a[9]<>15) then exit(false);
if (a[1]+a[5]+a[9]<>15) then exit(false);
if (a[3]+a[5]+a[7]<>15) then exit(false);
end;
begin
for i:=1 to 50 do
begin
readln(a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
fillchar(f,sizeof(f),true);
if check then begin writeln('0');goto 10; end;
b[1].q:=a;
t:=1;w:=1;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
while t<=w do
begin
swap(1,2);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(1,4);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(2,3);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(2,5);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(3,6);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(4,5);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(4,7);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(5,6);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(5,8);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(6,9);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(7,8);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(8,9);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
inc(t);
end;
writeln('-1');
10:
end;
end. -
0
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
int miao[1000000][4][4];
bool k[370000];
int step[1100000];
int jie[10];
int solve();
int ans[9]={0,69075,77577,135290,157121,205760,227591,285304,293806};
int kanto(int goal);
void copy(int goal1,int goal2);
int main()
{ jie[0]=1;
// freopen("1029.in","r",stdin);freopen("10291.out","w",stdout);
FOR(i,1,8) jie[i]=jie[i-1]*i;
FOR(w,1,50)
{ FOR(i,1,370000) k[i]=0;
FOR(i,1,3) FOR(j,1,3)
scanf("%d",&miao[1][i][j]);
int d =kanto(1);
k[d]=1;
int rbt=0;
FOR(i,1,9) if(d==ans[i]) {printf("0\n");rbt=1;}
if(!rbt) printf( "%d\n", solve() );}
return 0;
}int solve()
{
int head=0,end=1;
int d;
step[1]=0;
while(head<=end)
{
head++;
FOR(i,1,3) FOR(j,1,3)
{
if(i!=3)
{
swap(miao[head][i][j],miao[head][i+1][j]);
d=kanto(head);
if( ! k[d] )
{ end++; copy(head,end); k[d]=1; step[end]=step[head]+1;FOR(m,1,8) if(d==ans[m]) {/* FOR(q,1,3) FOR(w,1,3) printf("%d",miao[end][q][w]); printf("[]%d\n",d);*/return step[end];} }swap(miao[head][i][j],miao[head][i+1][j]);
}
if(j!=3)
{
swap(miao[head][i][j],miao[head][i][j+1]);
d=kanto(head);
if( !k[d] )
{ end++; copy(head,end); k[d]=1; step[end]=step[head]+1;FOR(m,1,8) if(d==ans[m]) { /* FOR(q,1,3) FOR(w,1,3) printf("%d",miao[end][q][w]); printf("[]%d\n",kanto(end));*/return step[end];}}
swap(miao[head][i][j],miao[head][i][j+1]);
}}
}
return -1;
}
int kanto(int goal)
{
int bala[10]={0,0,0,0,0,0,0,0,0,0},cc=0,d,f;
FOR(i,1,9) { f=0;
d=miao[goal][(i-1)/3+1][(i-1)%3+1]; bala[d]=1;
FOR(j,1,d) if(bala[j]==0) f++;
cc+=f*jie[9-i];
}
return cc+1;
}
void copy(int goal1,int goal2)
{
FOR( i,1,3) FOR( j,1,3) miao[goal2][i][j]=miao[goal1][i][j];
} -
0
第一次2700ms，没写好，第二次优化后
测试数据 #0: Accepted, time = 46 ms, mem = 5848 KiB, score = 10测试数据 #1: Accepted, time = 46 ms, mem = 5848 KiB, score = 10
测试数据 #2: Accepted, time = 62 ms, mem = 5844 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 5844 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 5848 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 5844 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 5844 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 5844 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 5844 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 5844 KiB, score = 10
Accepted, time = 540 ms, mem = 5848 KiB, score = 100
主要思想还是和各位一样，从目标状态开始搜，不过我优化了搜的过程，因为一个解可以通过7种变换生成另外七个解，所以只需要求bfs一个，然后其他的由变换生成出来就行，另外提交区里的一万两万毫秒的是怎么回事，乱写也不会那么慢吧。。。。。
代码200行而且丑，不贴了 -
0
我使用BFS，平均每一个测试点2s过。
太可恶了...一开始memout我废了九牛二猪之力终于控制好memeory不超了，结果又WA，我疯了似的检查代码~~~终于改好了.......~~~自己做数据一测，恩...都过，满意...于是果断提交，结果....Oh，Jesus！！！7个点AC，3个点TimelimitOut...于是我不满意地摇了摇头，优化了一下hash的时间.....终于...上帝保佑AC了~
以下是代码:
c
#include<stdio.h>//This programme was found by Lee simpson.
#define maxque 363879
char hash[9][9][9][9][9][9][9][9][9]={0};
struct node{
int map[3][3];
int step;
}que[363880],tmp,dd;
int swp(int *a,int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int judans(int n){
int i,j,a=0,b=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
a+=que[n].map[i][j];
b+=que[n].map[j][i];
}
if(a!=15||b!=15)
return 0;
a=0;
b=0;
}
for(i=0;i<3;i++){
a+=que[n].map[i][i];
b+=que[n].map[2-i][i];
}
if(a!=15||b!=15)
return 0;
return 1;
}
int judsam(int n){
dd=que[n];
if(hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]==0)
return 0;
return 1;
}
int tip(int n){
hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]=1;
}
int untip(int n){
hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]=0;
}
int main(){
int i,j,k,l,g,u,v,head=0,tail=0,xx[10]={1,0,-1,0},yy[10]={0,1,0,-1},used;
for(i=0;i<50;i++){
used=0;
head=0;
tail=0;
//memset(hash,0,sizeof(hash));
for(j=0;j<3;j++)
for(k=0;k<3;k++){
scanf("%d",&tmp.map[j][k]);
}
tmp.step=0;
que[head]=tmp;
tip(head);
while(head<=tail){
if(judans(head)==1){
printf("%d\n",que[head].step);
used=1;
break;
}
for(l=0;l<3;l++){
for(g=0;g<3;g++){
for(u=0;u<4;u++){
if(l+xx[u]>=0&&g+yy[u]>=0&&l+xx[u]<3&&g+yy[u]<3){
tmp=que[head];
swp(&tmp.map[l][g],&tmp.map[l+xx[u]][g+yy[u]]);
tmp.step++;
que[maxque]=tmp;
if(judsam(maxque)==0){
tip(maxque);
tail++;
que[tail]=tmp;
}
}
}
}
}
head++;
}
head=0;
while(head<=tail){
untip(head);
head++;
}
if(used==0){
printf("-1\n");
}
}
}
测试数据 #0: Accepted, time = 1937 ms, mem = 393800 KiB, score = 10
测试数据 #1: Accepted, time = 1765 ms, mem = 393800 KiB, score = 10
测试数据 #2: Accepted, time = 1765 ms, mem = 393800 KiB, score = 10
测试数据 #3: Accepted, time = 1890 ms, mem = 393800 KiB, score = 10
测试数据 #4: Accepted, time = 1828 ms, mem = 393800 KiB, score = 10
测试数据 #5: Accepted, time = 1968 ms, mem = 393804 KiB, score = 10
测试数据 #6: Accepted, time = 2234 ms, mem = 393800 KiB, score = 10
测试数据 #7: Accepted, time = 2171 ms, mem = 393804 KiB, score = 10
测试数据 #8: Accepted, time = 1812 ms, mem = 393804 KiB, score = 10
测试数据 #9: Accepted, time = 1687 ms, mem = 393800 KiB, score = 10
Accepted, time = 19057 ms, mem = 393804 KiB, score = 100 -
0
首先另外写一个暴搜把所有的结果状态找出来 总共八个
然后把这八个状态压进队列 BFS一次 hash判断是否重复 这里我用了Vector比较慢……
离线查询
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct status{
int x,dis;
status(int x,int dis):x(x),dis(dis){}
};const int dx[4]={3,-3,1,-1},mod=100007;
queue<status> q;
vector<int> h[100007];
int goal[60],ans[60],n=1,cnt=0;int shl(int x,int a){
for(int i=0;i<a;i++) x*=10;
return x;
}
int shr(int x,int a){
for(int i=0;i<a;i++) x/=10;
return x;
}void hash_insert(int x){h[x%mod].push_back(x);}
bool hash_find(int x){
int size=h[x%mod].size();
for(int i=0;i<size;i++)if(h[x%mod][i]==x) return true;
return false;
}int main(){
freopen("1029.in","r",stdin);freopen("1029.out","w",stdout);
q.push(status(276951438,0));hash_insert(276951438);
q.push(status(294753618,0));hash_insert(294753618);
q.push(status(438951276,0));hash_insert(438951276);
q.push(status(492357816,0));hash_insert(492357816);
q.push(status(618753294,0));hash_insert(618753294);
q.push(status(672159834,0));hash_insert(672159834);
q.push(status(816357492,0));hash_insert(816357492);
q.push(status(834159672,0));hash_insert(834159672);
while(scanf("%d",&goal[n])!=EOF){
int t;
for(int i=2;i<=9;i++) scanf("%d",&t),(goal[n]*=10)+=t;n++;
}n--;
for(int i=1;i<=n;i++) ans[i]=-1;
while(!q.empty()){
status t=q.front();q.pop();
for(int i=1;i<=n;i++)
if(t.x== goal[i])
ans[i]=t.dis,cnt++;
if(cnt==n) break;
for(int i=0;i<9;i++){
for(int j=0;j<4;j++){
int tmp=t.x;
if((i==2 || i==5) && j==2) continue;
if((i==3 || i==6) && j==3) continue;
if(i+dx[j]>=0 && i+dx[j]<9){
int Claris=tmp,a1,a2;
a1=shr(Claris,i)%10;
a2=shr(Claris,i+dx[j])%10;
tmp-=shl(a1,i);tmp-=shl(a2,i+dx[j]);
tmp+=shl(a1,i+dx[j]);tmp+=shl(a2,i);
if(!hash_find(tmp)) hash_insert(tmp),q.push(status(tmp,t.dis+1));
}
}
}
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
} -
0
chengchunyang LV 10 @ 10 年前
发一个我写的题解
http://blog.csdn.net/harlow_cheng/article/details/40454169
晴天小猪历险记之Number(5种写法，顺搜，逆搜，双向广搜,二叉搜索树(未加平衡树&加平衡树) -
0
评测结果
编译成功测试数据 #0: Accepted, time = 1125 ms, mem = 46460 KiB, score = 10
测试数据 #1: Accepted, time = 1046 ms, mem = 46464 KiB, score = 10
测试数据 #2: Accepted, time = 1109 ms, mem = 46464 KiB, score = 10
测试数据 #3: Accepted, time = 1218 ms, mem = 46460 KiB, score = 10
测试数据 #4: Accepted, time = 1062 ms, mem = 46464 KiB, score = 10
测试数据 #5: Accepted, time = 1109 ms, mem = 46460 KiB, score = 10
测试数据 #6: Accepted, time = 1187 ms, mem = 46464 KiB, score = 10
测试数据 #7: Accepted, time = 1187 ms, mem = 46464 KiB, score = 10
测试数据 #8: Accepted, time = 1125 ms, mem = 46464 KiB, score = 10
测试数据 #9: Accepted, time = 781 ms, mem = 46464 KiB, score = 10
Accepted, time = 10949 ms, mem = 46464 KiB, score = 100正向BFS+八维Hash=Accepted
var a:array[1..3,1..3] of longint;
b:array[1..100000,1..3,1..3] of longint;
c:array[1..9,1..9,1..9,1..9,1..9,1..9,1..9,1..9] of boolean;
s,sf,i,j,k,l,q,w,e,x,y,n,m:longint;
dd:boolean;
procedure pd(f:longint);//JianCe---------------------------------------
begin
if (b[f,1,1]+b[f,1,2]+b[f,1,3]=15)and(b[f,2,1]+b[f,2,2]+b[f,2,3]=15)
and(b[f,3,1]+b[f,3,2]+b[f,3,3]=15)and(b[f,1,1]+b[f,2,1]+b[f,3,1]=15)
and(b[f,1,2]+b[f,2,2]+b[f,3,2]=15)and(b[f,1,3]+b[f,2,3]+b[f,3,3]=15)
and(b[f,1,1]+b[f,2,2]+b[f,3,3]=15)and(b[f,3,1]+b[f,2,2]+b[f,1,3]=15)
then begin dd:=false;writeln(s);end;
end;
procedure aa(f:longint);//Hash-----------------------------------------
begin
c[b[f,1,1],b[f,1,2],b[f,1,3],b[f,2,1],b[f,2,2],b[f,2,3],b[f,3,1],
b[f,3,2]]:=true;
end;
procedure righ(x,y,z:longint);//WangYouTuoZhan-------------------------
var i,j,l,q,w,e:longint;
begin
inc(k);
for i:=1 to 3 do
for j:=1 to 3 do b[k,i,j]:=b[x,i,j];
e:=b[k,y,z];b[k,y,z]:=b[k,y,z+1];b[k,y,z+1]:=e;
if c[b[k,1,1],b[k,1,2],b[k,1,3],b[k,2,1],b[k,2,2],b[k,2,3],b[k,3,1],
b[k,3,2]] then begin dec(k);exit;end;
pd(k);aa(k);
end;
procedure down(x,y,z:longint);//WangXiaTuoZhan-------------------------
var i,j,l,q,w,e:longint;
begin
inc(k);
for i:=1 to 3 do
for j:=1 to 3 do b[k,i,j]:=b[x,i,j];
e:=b[k,y,z];b[k,y,z]:=b[k,y+1,z];b[k,y+1,z]:=e;
if c[b[k,1,1],b[k,1,2],b[k,1,3],b[k,2,1],b[k,2,2],b[k,2,3],b[k,3,1],
b[k,3,2]] then begin dec(k);exit;end;
pd(k);aa(k);
end;
begin//Main-----------------------------------------------------------
for sf:=1 to 50 do
begin
fillchar(b,sizeof(b),0); x:=1;y:=1;
fillchar(c,sizeof(c),false); s:=0;
for i:=1 to 3 do
for j:=1 to 3 do begin read(b[1,i,j]);a[i,j]:=b[1,i,j];end; dd:=true;
pd(1);aa(1);
while dd do
begin
k:=y;
inc(s);
for i:=x to y do
begin
for j:=1 to 3 do
for l:=1 to 2 do righ(i,j,l);
for j:=1 to 2 do
for l:=1 to 3 do down(i,j,l);
if not(dd) then break;
end;
x:=y+1;y:=k;
end;
end;
end. -
0
-
0
├ 测试数据 01：答案正确... (0ms, 67052KB)
├ 测试数据 02：答案正确... (0ms, 67052KB)
├ 测试数据 03：答案正确... (12ms, 67052KB)
├ 测试数据 04：答案正确... (4ms, 67052KB)
├ 测试数据 05：答案正确... (4ms, 67052KB)
├ 测试数据 06：答案正确... (12ms, 67052KB)
├ 测试数据 07：答案正确... (0ms, 67052KB)
├ 测试数据 08：答案正确... (0ms, 67052KB)
├ 测试数据 09：答案正确... (20ms, 67052KB)
├ 测试数据 10：答案正确... (0ms, 67052KB)
---|---|---|---|---|---|---|---|-
Accepted / 100 / 54ms / 67052KB对于一个3*3的矩阵，各种情况也不过9！=362880
而这里给出50个初始的乱矩阵，如果每次都正向找解，最恐怖就是50*9！=18144000，每次搜索可能经过的情况会有很多相同，不如离线操作，先记录有什么初始状态，再从初始的8个合法状态（可以事先dfs实现）进行bfs。再用了hash判状态，速度非常快。-
朋友可否把代码发给我看看，为什么我做不到那么快？
-
-
0
编译通过...
├ 测试数据 01：答案正确... (0ms, 19736KB)
├ 测试数据 02：答案正确... (0ms, 19736KB)
├ 测试数据 03：答案正确... (0ms, 19736KB)
├ 测试数据 04：答案正确... (0ms, 19736KB)
├ 测试数据 05：答案正确... (0ms, 19736KB)
├ 测试数据 06：答案正确... (0ms, 19736KB)
├ 测试数据 07：答案正确... (0ms, 19736KB)
├ 测试数据 08：答案正确... (0ms, 19736KB)
├ 测试数据 09：答案正确... (0ms, 19736KB)
├ 测试数据 10：答案正确... (0ms, 19736KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 0ms / 19736KBSBT + 双向BFS + 按层扩展...
......优哉游哉的分割线......-
朋友，可否把代码发给我看看？我写了很久的双向BFS都是3s左右。
-
^ambition
LV 8
@ 6 年前
