广搜
题意：有一个最大10*10的格盘，上面有一个标准色子。规定如果色子朝上的一面和相邻的某盘格的数字相同，或者盘格数字为-1，那么色子可以朝该方向滚动一格。问是否存在一条路径，使色子在格盘上从初始位置出发后，还能回到初始位置。若有解则数据保证只有唯一解。最后还要输出滚动方案。
这是1999年World Finals的C题……读完题面后很容易发现数据规模不大，状态转移不多，不需要特别优化。相比起来，需要花费更多时间考虑的是数据结构的表示。
色子有6面，但其姿态可以由正面和顶面两个数字来唯一确定，总共有6*4=24种可能。盘面最多100个格子，因此搜索空间是2400。可以将盘面状态表示为：((正面值-1)*6+(顶点值-1))*100+(纵坐标-1)*10+(横坐标-1)。当从队列中取出一个状态时，先由正面和顶点值得到整个色子当前6个面的值，这里可以将6个面分别编号，然后按六进制的方式（或者每个数用3位表示，移位处理）压成一个整型，再打表处理。然后模拟4个方向的滚动，求6个面的新值，再判断在该方向上的盘面值是否允许滚动。当回到原点时，返回当前状态以便回溯输出解方案。
|
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include<queue> #include<cstdio> #include<cstring> using namespace std; int r,c,r0,c0,d[3500],p[3500],t[10][10]; int mv[4][2]={-1,0,1,0,0,-1,0,1}; char s[21]; int a[6],b[6],id0; int id[35]={0,2540,3790,5065,6315,0,8835,0,11370,12605,0, 15140,16405,17645,0,0,21450,22690,23950,25230, 0,0,28985,30265,31520,0,34025,35310,0,37815,0, 40335,41605,42850,44120}; void rot(int l) { if(l==0) { b[0]=a[3]; b[1]=a[0]; b[2]=a[1]; b[3]=a[2]; b[4]=a[4]; b[5]=a[5]; } if(l==1) { b[0]=a[1]; b[1]=a[2]; b[2]=a[3]; b[3]=a[0]; b[4]=a[4]; b[5]=a[5]; } if(l==2) { b[0]=a[0]; b[1]=a[4]; b[2]=a[2]; b[3]=a[5]; b[4]=a[3]; b[5]=a[1]; } if(l==3) { b[0]=a[0]; b[1]=a[5]; b[2]=a[2]; b[3]=a[4]; b[4]=a[1]; b[5]=a[3]; } } void dec(int j) { int i; for(i=5;i>-1;i--) { a[i]=j%6+1; j/=6; } } int chk(int i,int j,int k) { if(i<0||i>=r||j<0||j>=c) return 0; if(!(t[i][j]==-1||t[i][j]==a[1])) return 0; if(d[i=(k*100+i*10+j)]) return 0; return i; } void init() { int i,j,k,l; scanf("%d%d%d%d%d%d",&r,&c,&r0,&c0,&i,&j); memset(d,0,sizeof d); memset(p,0,sizeof p); id0=(j-1)*6+i-1; for(i=0;i<r;i++) for(j=0;j<c;j++) scanf("%d",&t[i][j]); } int bfs() { int i,j,k,l,ri,ci; queue<int>Q; Q.push(id0*100+(r0-1)*10+c0-1); while(!Q.empty()) { i=Q.front(); Q.pop(); j=i%100; ri=j/10; ci=j%10; dec(id[i/100]); for(l=0;l<4;l++) { rot(l); j=(b[0]-1)*6+b[1]-1; if(k=chk(ri+mv[l][0],ci+mv[l][1],j)) { d[k]=d[i]+1; p[k]=i; if(ri+mv[l][0]==r0-1&&ci+mv[l][1]==c0-1) return k; Q.push(k); } } } return 0; } void dfs(int i) { int j,k,l=d[i]%9,ri,ci; j=i%100; ri=j/10+1; ci=j%10+1; if(ri==r0&&ci==c0) return; dfs(p[i]); if(l==0) printf(" "); printf("(%d,%d),",ri,ci); if(l==8) puts(""); } void solve() { int i=bfs(); puts(s); if(!i) { puts(" No Solution Possible"); return; } printf(" (%d,%d),",r0,c0); dfs(p[i]); if(d[i]%9==0) printf(" "); printf("(%d,%d)\n",r0,c0); } int main() { while(~scanf("%s",s)&&strcmp(s,"END")) { init(); solve(); } return 0; } |
一开始考虑时，直接用了全部六个面的值和坐标来作为状态，这样d和p数组的大小都是6^6*10*10=4665600，正常来说这也不是一个太大的值。但是这题test cases非常多。每次都memset的话，就超时了。因此只能在不丢失信息的情况下尽量压缩状态。