207 条题解
-
5
GGN_2015 LV 4 @ 2017-10-25 19:12:50
不明白为什么大家都在广搜..其实这题可以DFS啊..
因为同一种操作做四次等于没做，所以每种操作最多做三次。
分别枚举9种操作的操作次数就好了啊..
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; struct item{ int t[10]; bool empty(){ for(int i=1;i<=9;i++) if(t[i])return false; return true; } }; struct Queue{ int t[40],top; Queue(){ memset(t,0,sizeof(t));top=0; } void push(int x){t[++top]=x;} void output(){ for(int i=1;i<=top;i++) printf("%d ",t[i]); } }; bool operator<(Queue A,Queue B){ if(A.top!=B.top)return A.top<B.top; int i;for(i=1;i<=min(A.top,B.top);i++){ if(A.t[i]!=B.t[i]) return A.t[i]<B.t[i]; } return A.t[i]<B.t[i]; } item operator+(item A,item B){ for(int i=1;i<=9;i++) A.t[i]=(A.t[i]+B.t[i])%4; return A; } item operator*(item A,int time){ for(int i=1;i<=9;i++) A.t[i]=(A.t[i]*time)%4; return A; } Queue ans; item ope[12]; int cnt[10];bool suc=0; void DFS(int step){ if(step>9){ item now=ope[0]; for(int i=1;i<=9;i++) now=now+(ope[i]*cnt[i]); if(now.empty()){ if(ans.top==0) for(int i=1;i<=9;i++){ for(int j=1;j<=cnt[i];j++) ans.push(i); } else{ Queue n;n=Queue(); for(int i=1;i<=9;i++){ for(int j=1;j<=cnt[i];j++) n.push(i); } if(n<ans)ans=n; } } return; } for(int i=0;i<4;i++){ cnt[step]=i; DFS(step+1); } } int main(){ for(int i=1;i<=9;i++) scanf("%d",&ope[0].t[i]); ope[1]=(item){0,1,1,0,1,1,0,0,0,0};//ABDE ope[2]=(item){0,1,1,1,0,0,0,0,0,0};//ABC ope[3]=(item){0,0,1,1,0,1,1,0,0,0};//BCEF ope[4]=(item){0,1,0,0,1,0,0,1,0,0};//ADG ope[5]=(item){0,0,1,0,1,1,1,0,1,0};//BDEFH ope[6]=(item){0,0,0,1,0,0,1,0,0,1};//CFI ope[7]=(item){0,0,0,0,1,1,0,1,1,0};//DEGH ope[8]=(item){0,0,0,0,0,0,0,1,1,1};//GHI ope[9]=(item){0,0,0,0,0,1,1,0,1,1};//EFHI DFS(1); ans.output(); return 0; }-
YG666 @ 2018-05-20 20:23:54
太强了
-
-
0
Sky1231 (sky1231) LV 10 @ 2020-11-26 11:14:21
#include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> #include <deque> using namespace std; namespace dts { const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; const int o[9][9]={ {1,1,0,1,1,0,0,0,0}, {1,1,1,0,0,0,0,0,0}, {0,1,1,0,1,1,0,0,0}, {1,0,0,1,0,0,1,0,0}, {0,1,0,1,1,1,0,1,0}, {0,0,1,0,0,1,0,0,1}, {0,0,0,1,1,0,1,1,0}, {0,0,0,0,0,0,1,1,1}, {0,0,0,0,1,1,0,1,1} }; int clk[9],act,ans[9]; int chk(int *sta) { int flag=1; for (int i=0;i<9&&flag;i++) flag&=(sta[i]==0); return flag; } void dfs(int pos,int *sta,int *cnt,int oct) { if (chk(sta)&&oct<act) { act=oct,memcpy(ans,cnt,sizeof(ans)); return; } for (int i=3;i>=0&&pos<9&&oct<act;i--) { cnt[pos]=i; for (int j=0;j<9;j++) sta[j]=(sta[j]+o[pos][j]*i)%4; dfs(pos+1,sta,cnt,oct+i); for (int j=0;j<9;j++) sta[j]=((sta[j]-o[pos][j]*cnt[pos])%4+4)%4; cnt[pos]=0; } } void main() { for (int i=0;i<9;i++) scanf("%d",&clk[i]); act=oo_max; int bg[9]; memset(bg,0,sizeof(bg)); dfs(0,clk,bg,0); for (int i=0;i<9;i++) for (int j=1;j<=ans[i];j++) printf("%d ",i+1); } } int main() { dts::main(); } -
0
练DFS上手题，详见代码。
#include<bits/stdc++.h> using namespace std ; //Vijos P1016 const int way[9][9] = {{1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0} , {1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0} , {0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0} , {1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0} , {0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0} , {0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 1} , {0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0} , {0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1} , {0 , 0 , 0 , 0 , 1 ,1 , 0 , 1 , 1}} ;//9种方式改变不同的钟，1代表加3点，0代表不变 bool judge ;//判断是否调整完成 int x[9] , ans[9] ; void dfs(int num) { if (num == 9)//9种方式全部搜完 { for (int i = 0 ; i < 9 ; i ++) { if (x[i] % 4 != 0)//有不是12点的钟 return ; } judge = true ;//全部调整完成 return ; } for (int i = 0 ; i <= 3 ; i ++) { ans[num] = i ;//第（i+1）钟方式的数量 for (int j = 0 ; j < 9 ; j ++) { x[j] += way[num][j] * i ;//改变 } dfs(num + 1) ;//深搜 if (judge)//此时已经调整完成，而调整方式有且只有一种，因此可以输出答案 return ; for (int j = 0 ; j < 9 ; j ++) { x[j] -= way[num][j] * i ;//回溯 } } } int main() { for (int i = 0 ; i < 9 ; i ++) { cin >> x[i] ; } dfs(0) ; for (int i = 0 ; i < 9 ; i ++) { for (int j = 0 ; j < ans[i] ; j ++) { cout << i + 1 << ' ' ; } } cout << endl ; } -
0
直接暴力bfs搜索就好了
其实还有枚举的办法
很经典的题目
记得那本《算法竞赛宝典》上有仔细讲
因为不太难
直接上bfs的代码啦~‘
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef int stade[9]; stade start; int head,tail; stade goal={0}; stade l; int Rank[1000000]; int c[1000000]; bool s[4][4][4][4][4][4][4][4][4]; stade q[1000000]; int da[9][9] = { {0, 1, 3, 4, -1 }, {0, 1, 2, -1 }, {1, 2, 4, 5, -1 }, {0, 3, 6, -1 }, {1,3,4,5,7,-1}, {2,5,8,-1}, {3,4,6,7,-1}, {6,7,8,-1}, {4,5,7,8,-1} }; void Out(int x) { if(x>1) { Out(Rank[x]); cout<<c[x]<<" "; } } void change(stade &p,int x) { memcpy(&l,&p,sizeof(p)); for(int i=0;da[x][i]!=-1;i++) { l[da[x][i]]++; l[da[x][i]]%=4; } } bool check(stade po) { if(s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]] [po[6]][po[7]][po[8]]==0) return 1; else return 0; } void check1(stade po) { s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]] [po[6]][po[7]][po[8]]=1; } void bfs() { memcpy(&q[head],&start,sizeof(start)); tail++; check1(start); while(head<=tail) { stade &p=q[head]; for(int i=0;i<=8;i++) { change(p,i); if(check(l)) { memcpy(&q[tail],&l,sizeof(l)); Rank[tail]=head; c[tail]=i+1; check1(l); if(memcmp(goal,l,sizeof(l))==0) { Out(tail); return; } tail++; } } head++; } } int main() { for(int i=0;i<=8;i++) { int x; cin>>x; start[i]=(x/3)%4; } bfs(); return 0; } -
0
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<queue> using namespace std; const int L=1<<18; //18位二进制串压状态 queue<int>Q; int c[9]; bool vis[L]; struct last{ int lst; int opt; }; last b[L]; int getst() { int ret=0; for (int s=0;s<9;s++) ret|=c[s]<<(s<<1); return ret; } int rot(int k,int wis) { k=(~(0x3<<(wis<<1))&k)|((((k&(0x3<<(wis<<1)))>>(wis<<1))+1)%4)<<(wis<<1); return k; //位运算拨钟 } int r[9][5]={ {0,1,3,4,-1}, {0,1,2,-1,-1}, {1,2,4,5,-1}, {0,3,6,-1,-1}, {1,3,4,5,7}, {2,5,8,-1,-1}, {3,4,6,7,-1}, {6,7,8,-1,-1}, {4,5,7,8,-1} }; void bfs(int x) { Q.push(x); vis[x]=1; b[x].lst=-1; b[x].opt=-1; while (!Q.empty()) { int k=Q.front(); Q.pop(); if (!k) return; for (int s=0;s<9;s++) { int kk=k; for (int t=0;t<5;t++) if (r[s][t]!=-1) kk=rot(kk,r[s][t]); if (!vis[kk]) { vis[kk]=1; Q.push(kk); b[kk].lst=k; b[kk].opt=s+1; } } } } int path[L],count=0; void back(int x) { path[count++]=b[x].opt; if (b[x].lst!=-1) back(b[x].lst); } int main() { memset(vis,0,sizeof(vis)); memset(b,0,sizeof(b)); for (int s=0;s<9;s++) scanf("%d",&c[s]); int q=getst(); bfs(q); back(0); for (int s=count-2;s>=0;s--) printf("%d ",path[s]); } -
0
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; bool flag[4][4][4][4][4][4][4][4][4]; int op[10][10] = {{0},{1,2,4,5},{1,2,3},{2,3,5,6},{1,4,7},{2,4,5,6,8}, {3,6,9},{4,5,7,8},{7,8,9},{5,6,8,9}}; int st[10]; struct node { int state[10],step,ans[200]; friend bool operator < (struct node a,struct node b) { return a.step > b.step; } }s,now; void bfs() { priority_queue<node> Q; memset(flag,0,sizeof(flag)); memcpy(s.state,st,sizeof(st)); s.step = 0; flag[st[1]][st[2]][st[3]][st[4]][st[5]][st[6]][st[7]][st[8]][st[9]] = 1; Q.push(s); while(!Q.empty()) { now = Q.top(); Q.pop(); for(int i = 1;i <= 9;i ++) { s = now; for(int j = 0;op[i][j];j ++) { s.state[op[i][j]] ++; if(s.state[op[i][j]] >= 4) s.state[op[i][j]] -= 4; } if(!flag[s.state[1]][s.state[2]][s.state[3]][s.state[4]][s.state[5]][s.state[6]][s.state[7]][s.state[8]][s.state[9]]) { s.ans[++s.step] = i; flag[s.state[1]][s.state[2]][s.state[3]][s.state[4]][s.state[5]][s.state[6]][s.state[7]][s.state[8]][s.state[9]] = 1; Q.push(s); } if(!s.state[1] && !s.state[2] && !s.state[3] && !s.state[4] && !s.state[5] && !s.state[6] && !s.state[7] && !s.state[8] && !s.state[9]) { sort(s.ans+1,s.ans + s.step+1); for(int j = 1;j <= s.step;j ++) printf("%d ",s.ans[j]); exit(0); } } } } int main() { for (int i=1;i<=9;i++) scanf("%d",&st[i]); bfs(); return 0; }楼下真6
-
0
测试数据 #0: Accepted, time = 62 ms, mem = 15152 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 15148 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 15152 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 15148 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 15148 KiB, score = 10
测试数据 #5: Accepted, time = 125 ms, mem = 15148 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 15148 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 15148 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 15148 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 15152 KiB, score = 10
Accepted, time = 511 ms, mem = 15152 KiB, score = 100
呵呵，猥琐的时间 -
0
const dd:array[1..9,1..9] of integer=
((1,1,0,1,1,0,0,0,0),
(1,1,1,0,0,0,0,0,0),
(0,1,1,0,1,1,0,0,0),
(1,0,0,1,0,0,1,0,0),
(0,1,0,1,1,1,0,1,0),
(0,0,1,0,0,1,0,0,1),
(0,0,0,1,1,0,1,1,0),
(0,0,0,0,0,0,1,1,1),
(0,0,0,0,1,1,0,1,1));
var i,j,l,h:longint;
a:array[0..300001,0..10] of longint;
o:array[0..300001] of longint;
flag:array[0..3,0..3,0..3,0..3,0..3,0..3,0..3,0..3,0..3] of boolean;
procedure tof;
var t:longint;
begin
for j:=1 to 9 do
if a[h,j]<>0 then exit;
t:=h;
for j:=o[0] downto 1 do write(o[j],' ');
halt;
end;
begin
readln(a[1,1],a[1,2],a[1,3]);
readln(a[1,4],a[1,5],a[1,6]);
readln(a[1,7],a[1,8],a[1,9]);
l:=1;
h:=1;
while l<=h do
begin
for i:=1 to 9 do
begin
a[0]:=a[l];
for j:=1 to 9 do
a[0,j]:=(a[0,j])mod 3;
if not flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8]] then
begin
inc(h);
a[h]:=a[0];
flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8],a[0,9]]:=true;
a[h,0]:=l;
a[h,10]:=i;
tof;
end;
end; inc(l);
end;
end.
深搜要栈溢出！
记住用“堆空间”——宽搜！
注意扩展数量!-
陈兆锋 @ 2016-07-17 14:09:46
错了，说代码是要高亮语法，例：（1014我的代码）
program s;
var a:array[1..1000] of record x,y:int64; end;
var b,c:longint;
procedure d(e,f:longint);
var g,h,i,j:longint;
begin
g:=e;
h:=f;
i:=a[(g+h) div 2].x;
repeat
while a[g].x<i do
g:=g+1;
while a[h].x>i do
h:=h-1;
if g<=h then begin
j:=a[g].x;
a[g].x:=a[h].x;
a[h].x:=j;
j:=a[g].y;
a[g].y:=a[h].y;
a[h].y:=j;
g:=g+1;
h:=h-1;
end;
until g>h;
if g<f then d(g,f);
if e<h then d(e,h);
end;
var k,l:array[0..1000,0..1000] of extended;
var m,n:extended;
var o,p:longint;
var q,r:int64;
begin
readln(b);
for c:=1 to b do
readln(a[c].x,a[c].y);
if b>0 then d(1,b);
for c:=1 to b-1 do
for o:=c+1 to b do
begin
if a[c].x>a[o].x then q:=a[c].x-a[o].x
else q:=a[o].x-a[c].x;
if a[c].y>a[o].y then r:=a[c].y-a[o].y
else r:=a[o].y-a[c].y;
l[c,o]:=sqrt(q*q+r*r);
end;
for c:=1 to b do
for o:=1 to b do
k[c,o]:=1e24;
if b>=2 then k[2,1]:=l[1,2]
else begin
writeln('0.00');
exit;
end;
for c:=3 to b do
for o:=1 to c-1 do
if o<c-1 then k[c,o]:=k[c-1,o]+l[c-1,c]
else for p:=1 to o-1 do
begin
n:=k[o,p]+l[p,c];
if n<k[c,o] then k[c,o]:=n;
end;
writeln(k[b,b-1]+l[b-1,b]:0:2);
end. -
不对，是这样：
Pascal
program s;
var a:array[1..1000] of record x,y:int64; end;
var b,c:longint;
procedure d(e,f:longint);
var g,h,i,j:longint;
begin
g:=e;
h:=f;
i:=a[(g+h) div 2].x;
repeat
while a[g].x<i do
g:=g+1;
while a[h].x>i do
h:=h-1;
if g<=h then begin
j:=a[g].x;
a[g].x:=a[h].x;
a[h].x:=j;
j:=a[g].y;
a[g].y:=a[h].y;
a[h].y:=j;
g:=g+1;
h:=h-1;
end;
until g>h;
if g<f then d(g,f);
if e<h then d(e,h);
end;
var k,l:array[0..1000,0..1000] of extended;
var m,n:extended;
var o,p:longint;
var q,r:int64;
begin
readln(b);
for c:=1 to b do
readln(a[c].x,a[c].y);
if b>0 then d(1,b);
for c:=1 to b-1 do
for o:=c+1 to b do
begin
if a[c].x>a[o].x then q:=a[c].x-a[o].x
else q:=a[o].x-a[c].x;
if a[c].y>a[o].y then r:=a[c].y-a[o].y
else r:=a[o].y-a[c].y;
l[c,o]:=sqrt(q*q+r*r);
end;
for c:=1 to b do
for o:=1 to b do
k[c,o]:=1e24;
if b>=2 then k[2,1]:=l[1,2]
else begin
writeln('0.00');
exit;
end;
for c:=3 to b do
for o:=1 to c-1 do
if o<c-1 then k[c,o]:=k[c-1,o]+l[c-1,c]
else for p:=1 to o-1 do
begin
n:=k[o,p]+l[p,c];
if n<k[c,o] then k[c,o]:=n;
end;
writeln(k[b,b-1]+l[b-1,b]:0:2);
end.
-
代码错了，编译不通过，漏了a[0,9]，应该是not flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8],a[0,9]]
-
-
0
tootal (hzq) LV 9 @ 2016-05-18 13:22:09
位运算+暴力搜索
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
const int N = 9,M = 3,Z = 28;
int TG[M][M],G[M][M],m = Z;
int P[N] = {432,448,216,292,186,73,54,7,27};
unsigned long long int A = 0,B;
int MP[N];
void read()
{
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
{
scanf("%d",&TG[i][j]);
G[i][j] = TG[i][j];
}
}
bool is_ok()
{
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
if(G[i][j] % (M + 1)) return false;
return true;
}
int times(unsigned long long int X,int i)
{
return (((X >> ((N << 1) - (i << 1)) - 1) & 1) << 1) + ((X >> (N << 1) - (i << 1) - 2) & 1);
}
void move()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < times(A,i);j++)
for(int k = 0;k < N;k++)
if((P[i] >> (N - k - 1)) & 1) G[k / M][k % M]++;
}
void write()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < times(B,i);j++) printf("%d ",i + 1);
}
void dfs()
{
while(1)
{
A++;
if(A > (1 << ((N << 1) + 1))) break;
int t = 0;
for(int i = 0;i < N;i++) t += times(A,i);
if(t < m)
{
move();
if(is_ok())
{
m = t;
B = A;
}
}
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
G[i][j] = TG[i][j];
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
read();
dfs();
write();
printf("\n");
//printf("Time : %.3f\n",(double)clock() / CLOCKS_PER_SEC);
return 0;
} -
0
//暴搜
const a:array[1..9,0..9] of integer=((4,1,2,4,5,0,0,0,0,0),
(3,1,2,3,0,0,0,0,0,0),
(4,2,3,5,6,0,0,0,0,0),
(3,1,4,7,0,0,0,0,0,0),
(5,2,4,5,6,8,0,0,0,0),
(3,3,6,9,0,0,0,0,0,0),
(4,4,5,7,8,0,0,0,0,0),
(3,7,8,9,0,0,0,0,0,0),
(4,5,6,8,9,0,0,0,0,0));
var b,c,ans:array[0..46] of integer;
i,j,k:integer;procedure bc;
var s,i,j,u:integer;
begin
s:=0;
u:=0;
for i:=1 to 9 do
inc(s,c[i]);
if s<ans[0] then
for i:=1 to 9 do
ans[i]:=c[i];
if s<ans[0] then ans[0]:=s;
end;procedure pd;
var i:integer;
begin
for i:=1 to 9 do
if b[i]<>12 then exit;
bc;
end;procedure xz(x:integer);
var i:integer;
begin
for i:=1 to a[x,0] do
begin
inc(b[a[x,i]],3);
if b[a[x,i]]>12 then dec(b[a[x,i]],12);
end;
end;procedure ymz(k:integer);
var i:integer;
begin
if k>9 then pd else
begin
ymz(k+1);
for i:=1 to 3 do
begin
xz(k);
inc(c[k]);
ymz(k+1);
end;
xz(k);
c[k]:=0;
end;
end;begin
ans[0]:=27;
for i:=1 to 9 do
read(b[i]);
ymz(1);
for i:=1 to 9 do
if ans[i]<>0 then
for j:=1 to ans[i] do
write(i,' ');
end. -
0
program abcdefg;
var
i1,i2,i3,i4,i5,i6,i7,i8,i9,c,i:longint;
j1,j2,j3,j4,j5,j6,j7,j8,j9:longint;
a,aa:array[1..9]of longint;
begin
for i:=1 to 3 do
read(aa[i]);
for i:=4 to 6 do
read(aa[i]);
for i:=7 to 9 do
read(aa[i]);
for j1:=0 to 3 do
for j2:=0 to 3 do
for j3:=0 to 3 do
for j4:=0 to 3 do
for j5:=0 to 3 do
for j6:=0 to 3 do
for j7:=0 to 3 do
for j8:=0 to 3 do
for j9:=0 to 3 do
begin
for i:=1 to 9 do a[i]:=aa[i];
a[1]:=(a[1]+j1+j2+j4) mod 4;
a[2]:=(a[2]+j1+j2+j3+j5) mod 4;
a[3]:=(a[3]+j3 3 2+j3+j6) mod 4;
a[4]:=(a[4]+j1+j4+j5+j7) mod 4;
a[5]:=(a[5]+j1+j3+j5+j7+j9) mod 4;
a[6]:=(a[6]+j3+j5+j6+j9) mod 4;
a[7]:=(a[7]+j4+j7+j8) mod 4;
a[8]:=(a[8]+j5+j7+j8+j9) mod 4;
a[9]:=(a[9]+j6+j8+j9) mod 4;
if (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9])=0 then
begin
for i:=1 to j1 do
write(1,' ');
for i:=1 to j2 do
write(2,' ');
for i:=1 to j3 do
write(3,' ');
for i:=1 to j4 do
write(4,' ');
for i:=1 to j5 do
write(5,' ');
for i:=1 to j6 do
write(6,' ');
for i:=1 to j7 do
write(7,' ');
for i:=1 to j8 do
write(8,' ');
for i:=1 to j9 do
write(9,' ');
end;
end;
end. -
0
wang_yanheng LV 10 @ 2015-11-01 11:40:04
为什么全是暴力算法
这题应该用 位运算压缩状态+记忆化BFS 才对
因为只有9个钟，每个钟只有0～3四种状态，故可用18为的二进制来表示所有钟的状态。（每两位存一个钟）目标状态为全0。
移动时，把被操作钟的那两位从状态里提出来，+1，去掉进位，再压回状态中。
程序中 & 3 就是拿来去掉进位用的，因为3的二进制为00000011。
由于要输出路径，所以记录一下状态的转移即可，递归输出。//vijos p1016
#include <stdio.h>#define END -1
#define STATUS 0
#define STEP 1short moves[9][6] = {
{0, 1, 3, 4, END},
{0, 1, 2, END},
{1, 2, 4, 5, END},
{0, 3, 6, END},
{1, 3, 4, 5, 7, END},
{2, 5, 8, END},
{3, 4, 6, 7, END},
{6, 7, 8, END},
{4, 5, 7, 8, END},
};short searched[1<<20];
int queue[1<<20][2];
int prevStatus[1<<20];
int prevMove[1<<20];
int head, tail;void print(int status){
if(prevStatus[status] == END)
return;
print(prevStatus[status]);
printf("%d ", prevMove[status]+1);
}
int addToQueue(int status, int step){
if(!searched[status]){
searched[status] = 1;
queue[tail][STATUS] = status;
queue[tail][STEP] = step;
tail++;
return 1;
}
return 0;
}
void bfs(int initStatus){
int status, step, i, j, k, tmp;
head = tail = 0;
addToQueue(initStatus, 0);
while(head < tail){
status = queue[head][STATUS];
step = queue[head][STEP];
if(status == 0)
break;
for(i=0; i<9; i++){
tmp = status;
for(j=0; moves[i][j]!=END; j++){
tmp &= ((1<<18)-1) ^ (3 << (2*(8-moves[i][j])));
k = (status >> (2*(8-moves[i][j]))) & 3;
tmp |= ((k+1) & 3) << (2*(8-moves[i][j]));
}
if(addToQueue(tmp, step+1)){
prevStatus[tmp] = status;
prevMove[tmp] = i;
}
}
head++;
}
print(0);
}
int main(){
int i, k, tmp, status;
status = 0;
for(i=0; i<3; i++){
for(k=0; k<3; k++){
status <<= 2;
scanf("%d", &tmp);
status |= tmp;
}
}
for(i=0; i<(1<<20); i++){
searched[i] = 0;
prevStatus[i] = prevMove[i] = END;
}
bfs(status);
printf("\n");
return 0;
}-
1464942666 @ 2016-07-06 16:40:56
你倒是讲讲 位运算 原理啊。BFS是人都会啊。
-
-
0
#include<cstdio>
#include<cstring>
using namespace std;
int map[10],tmp[30],answer[50],ans;
void turn(int x,int y)
{
map[x]=(map[x]+y)%4;
}
bool check()
{
for(int i=1;i<=9;i++)
{
if(map[i]>0)return 0;
}return 1;
}
void search(int x,int cnt)
{
if(cnt>=ans)return;
if(x==10)
{
if(!check())return;
ans=cnt;
for(int i=1;i<=cnt;i++)answer[i]=tmp[i];
}
else
{
for(int i=3;i>=0;i--)
{
if(x==1 || x==2 || x==4)turn(1,i);
if(x==1 || x==2 || x==3 || x==5)turn(2,i);
if(x==2 || x==3 || x==6)turn(3,i);
if(x==1 || x==4 || x==5 || x==7)turn(4,i);
if(x==1 || x==3 || x==5 || x==7 || x==9)turn(5,i);
if(x==3 || x==5 || x==6 || x==9)turn(6,i);
if(x==4 || x==7 || x==8 )turn(7,i);
if(x==5 || x==7 || x==8 || x==9)turn(8,i);
if(x==6 || x==8 || x==9 )turn(9,i);
for(int j=cnt+1;j<=cnt+i;j++)tmp[j]=x;search(x+1,cnt+i);
if(x==1 || x==2 || x==4)turn(1,4-i);
if(x==1 || x==2 || x==3 || x==5)turn(2,4-i);
if(x==2 || x==3 || x==6)turn(3,4-i);
if(x==1 || x==4 || x==5 || x==7)turn(4,4-i);
if(x==1 || x==3 || x==5 || x==7 || x==9)turn(5,4-i);
if(x==3 || x==5 || x==6 || x==9)turn(6,4-i);
if(x==4 || x==7 || x==8 )turn(7,4-i);
if(x==5 || x==7 || x==8 || x==9)turn(8,4-i);
if(x==6 || x==8 || x==9 )turn(9,4-i);
for(int j=cnt+1;j<=cnt+i;j++)tmp[j]=0;
}
}
}
int main()
{
int n,i,m,j;
for(i=1;i<=9;i++)scanf("%d",&map[i]);
ans=99999999;
search(1,0);
for(i=1;i<=ans;i++)printf("%d ",answer[i]);
printf("\n");
return 0;
} -
0
暴力搜索就能过的嘛~ 现代计算机果然性能强劲!
#include <iostream> const size_t NUMBER_OF_CLOCKS = 9; const size_t NUMBER_OF_OPERATIONS = 9; /** * 最大操作次数. * 由于操作4次会回到原点, 没有必要继续搜索. */ const size_t MAX_NUMBER_OF_OPERATIONS = 4; /** * 获取当前对各个时钟操作的次数. * @return 对各个时钟操作的次数 */ int getOperationTimes(int* operations) { int operationTimes = 0; for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) { operationTimes += operations[i]; } return operationTimes; } /** * 获取最优的调整方案 * @param clocks - 当前每个时钟的时间([0, 4)的整数) * @param bestOperations - 对各个时钟最佳操作的次数 * @return 每个操作进行次数的数组 */ void getBestSolution(int* clocks, int* bestOperations) { /** * 存储时钟的初始状态. * 用于回溯, 在搜索失败后的rollback. */ int mirrorClocks[NUMBER_OF_CLOCKS] = {0}; /** * 存储对时钟的操作. */ int operations[NUMBER_OF_OPERATIONS][NUMBER_OF_CLOCKS] = { { 1, 1, 0, 1, 1, 0, 0, 0, 0 }, { 1, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 1, 1, 0, 0, 0 }, { 1, 0, 0, 1, 0, 0, 1, 0, 0 }, { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 0, 0, 1, 0, 0, 1, 0, 0, 1 }, { 0, 0, 0, 1, 1, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 0, 1, 1, 0, 1, 1 } }; /** * 存储当前对各时钟操作的计数. * 记录对每个时钟操作的次数. */ int currentOperations[NUMBER_OF_CLOCKS] = {0}; for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) { mirrorClocks[i] = clocks[i]; } for ( currentOperations[0] = 0 ; currentOperations[0] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[0] ) { for ( currentOperations[1] = 0 ; currentOperations[1] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[1] ) { for ( currentOperations[2] = 0 ; currentOperations[2] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[2] ) { for ( currentOperations[3] = 0 ; currentOperations[3] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[3] ) { for ( currentOperations[4] = 0 ; currentOperations[4] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[4] ) { for ( currentOperations[5] = 0 ; currentOperations[5] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[5] ) { for ( currentOperations[6] = 0 ; currentOperations[6] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[6] ) { for ( currentOperations[7] = 0 ; currentOperations[7] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[7] ) { for ( currentOperations[8] = 0 ; currentOperations[8] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[8] ) { // Rollback for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) { clocks[i] = mirrorClocks[i]; } bool isSuccessful = true; for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) { for ( size_t j = 0; j < NUMBER_OF_OPERATIONS; ++ j ) { clocks[i] += currentOperations[j] * operations[j][i]; } clocks[i] %= 4; if ( clocks[i] != 0 ) { isSuccessful = false; break; } } if ( !isSuccessful ) { continue; } // Save the solution int currentOperationTimes = getOperationTimes(currentOperations); int bestOperationTimes = getOperationTimes(bestOperations); if ( currentOperationTimes < bestOperationTimes ) { for ( size_t i = 0; i < NUMBER_OF_OPERATIONS; ++ i ) { bestOperations[i] = currentOperations[i]; } } } } } } } } } } } } int main() { /** * 存储时钟当前的状态. * 在搜索时不断改变. */ int clocks[NUMBER_OF_CLOCKS] = {0}; /** * 存储当前对各时钟操作计数的最优解. */ int bestOperations[NUMBER_OF_OPERATIONS] = { 10, 10, 10, 10, 10, 10, 10, 10, 10 }; for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) { std::cin >> clocks[i]; } getBestSolution(clocks, bestOperations); for ( size_t i = 0; i < NUMBER_OF_OPERATIONS; ++ i ) { for ( int j = 0; j < bestOperations[i]; ++ j ) { std::cout << ( i + 1 ) << " "; } } std::cout << std::endl; return 0; } -
0
var
aa,a:array[1..9]of integer;
i1,i2,i3,i4,i5,i6,i7,i8,i9:integer;
i,j:integer;
begin
fillchar(b,sizeof(b),0);
for i:=1 to 9 do
read(a[i]);
for i1:=0 to 3 do
for i2:=0 to 3 do
for i3:=0 to 3 do
for i4:=0 to 3 do
for i5:=0 to 3 do
for i6:=0 to 3 do
for i7:=0 to 3 do
for i8:=0 to 3 do
for i9:= 0 to 3 do
begin
for i:=1 to 9 do
aa[i]:=a[i];
aa[1]:=(aa[1]+i1+i2+i4) mod 4;
aa[2]:=(aa[2]+i1+i2+i3+i5) mod 4;
aa[3]:=(aa[3]+i2+i3+i6) mod 4;
aa[4]:=(aa[4]+i1+i4+i5+i7) mod 4;
aa[5]:=(aa[5]+i1+i3+i5+i7+i9) mod 4;
aa[6]:=(aa[6]+i3+i5+i6+i9) mod 4;
aa[7]:=(aa[7]+i4+i7+i8) mod 4;
aa[8]:=(aa[8]+i5+i7+i8+i9) mod 4;
aa[9]:=(aa[9]+i6+i8+i9) mod 4;
if (aa[1]+aa[2]+aa[3]+aa[4]+aa[5]+aa[6]+aa[7]+aa[8]+aa[9]=0) then
begin
for j:=1 to i1 do
write(1,' ');
for j:=1 to i2 do
write(2,' ');
for j:=1 to i3 do
write(3,' ');
for j:=1 to i4 do
write(4,' ');
for j:=1 to i5 do
write(5,' ');
for j:=1 to i6 do
write(6,' ');
for j:=1 to i7 do
write(7,' ');
for j:=1 to i8 do
write(8,' ');
for j:=1 to i9 do
write(9,' ');
writeln;
halt;
end;
end;
end. -
0
###75ms
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<time.h>
#include<stdlib.h>
using namespace std;
int a[9][9] = {
{0, 1, 3, 4, -1 },
{0, 1, 2, -1 },
{1, 2, 4, 5, -1 },
{0, 3, 6, -1 },
{1,3,4,5,7,-1},
{2,5,8,-1},
{3,4,6,7,-1},
{6,7,8,-1},
{4,5,7,8,-1}
};
int c[9];
int o[9];
int mi;
int ans[9];
bool ok(){
int i;
for (i = 0; i < 9; i++)if (c[i])return false;
return true;
}
void change(int op){
int i;
for (i = 0; a[op][i]!=-1; i++){
c[a[op][i]]++;
c[a[op][i]] %= 4;
}
}
void go(int op, int now){
if (ok()){
mi = now;
memcpy(ans, o, sizeof(o));
return;
}
if (op==9||now>=mi)return;
int i;
for (i = 0; i < 4; i++,change(op)){
o[op] = i;
go(op + 1, now + i);
}
o[op] = 0;
}
int main(){
int i;
for (i = 0; i < 9; i++)cin >> c[i];
mi = 27;
go(0, 0);
for (i = 0; i < 9; i++){
while (ans[i]--)
cout << i + 1 << " ";
}
return 0;
} -
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>using namespace std;
int a[10],b[10][10]={{0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
void find()
{
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool flag=true;
for (int i=1; i<=9; i++) a[i]=d[i];
for (int i=1; i<=9; i++)
{
for (int j=1; j<=9; j++) a[i]+=c[j]*b[j][i];
a[i]%=4;
if (a[i]!=0) {flag=false; break;}
}
if (flag)
{
int ss=0;
for (int i=1; i<=9; i++) ss+=c[i];
if (ss<m) ss=m;
for(int i=1; i<=9; i++) e[i]=c[i];
}
}
}
int main()
{
for(int i=1; i<=9; i++)
{
cin>>a[i];
d[i]=a[i];
}
find();
bool flag=false;
for(int i=1;i<=9;i++)
for(int j=1; j<=e[i]; j++)
{
if(flag) cout<<" "; else flag=true;
cout<<i;
}
return 0;
} -
0
#include<iostream>
using namespace std;
int a[10],b[10][10]={{0},{0,1,1,0,1,1,0,0,0,0},{0,1,1,1,0,0,0,0,0,0},{0,0,1,1,0,1,1,0,0,0},{0,1,0,0,1,0,0,1,0,0},{0,0,1,0,1,1,1,0,1,0},{0,0,0,1,0,0,1,0,0,1},{0,0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
main()
{
for(int i=1;i<=9;i++)
{
cin>>a[i];
d[i]=a[i];
}
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool bo=1;
for(int i=1;i<=9;i++)
a[i]=d[i];
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
a[i]+=c[j]*b[j][i];
a[i]%=4;
if(a[i]!=0)
{
bo=0;
break;
}
}
if(bo)
{
int ss=0;
for(int i=1;i<=9;i++)
ss+=c[i];
if(ss<m)
ss=m;
for(int i=1;i<=9;i++)
e[i]=c[i];
}
}
bool bo=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=e[i];j++)
{
if(bo)
cout<<" ";
else
bo=1;
cout<<i;
}
} -
0
#include<iostream>
#include<cstring>
using namespace std;
int a[10],b[10][10]={{0},{0,1,1,0,1,1,0,0,0,0},{0,1,1,1,0,0,0,0,0,0},{0,0,1,1,0,1,1,0,0,0},{0,1,0,0,1,0,0,1,0,0},{0,0,1,0,1,1,1,0,1,0},{0,0,0,1,0,0,1,0,0,1},{0,0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
main()
{
for(int i=1;i<=9;i++)
{
cin>>a[i];
d[i]=a[i];
}
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool bo=1;
for(int i=1;i<=9;i++)
a[i]=d[i];
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
a[i]+=c[j]*b[j][i];
a[i]%=4;
if(a[i]!=0)
{
bo=0;
break;
}
}
if(bo)
{
int ss=0;
for(int i=1;i<=9;i++)
ss+=c[i];
if(ss<m)
ss=m;
for(int i=1;i<=9;i++)
e[i]=c[i];
}
}
bool bo=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=e[i];j++)
{
if(bo)
cout<<" ";
else
bo=1;
cout<<i;
}
}
GGN_2015
LV 4
@ 2017-10-25 19:12:50
信息
- ID
- 1016
- 难度
- 5
- 分类
- 搜索 | 搜索与剪枝 点击显示
- 标签
- 递交数
- 4799
- 已通过
- 1608
- 通过率
- 34%
- 被复制
- 19
- 上传者
-
Vivian Snow
