「BZOJ2719」[Violet 4] 银河之星
.gif)
.gif)
.gif)
.gif)
题解
容易发现 可以将平面的所有点分为9类
0 1 2
3 4 5
6 7 8
即同类棋子可以通过第三种移动到达相同位置
而一个棋子跨过另一个，如0跨过4到达8，则可以视为0和4可以合成8，则问题转换为能不将所有点通过一系列合成得到一个和目标格子同类的点
还要注意一下这种情况（1为棋子，0为目标，棋盘大小为3*3）
1 X X
X 0 X
X X 1
这种情况下是不能将0与8合成4的，除非将棋子移动到棋盘外
所以还需要处理出在当前的棋盘大小内，哪些棋子可以相互合成，可以枚举棋盘内所有格子得出
接着记忆化搜索即可T T
经检验，基本能秒过所有数据，测试数据的搜索范围似乎都不会超过1000 T T
我比较脑残搞了半天
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } map<ll,int> q; ll bin[15],bg,ed; int ans[1005]; int k,n,m,xt,yt,sz; int xx[4]={0,1,1,1},yy[4]={1,-1,0,1}; bool mp[10][10]; void add(int x1,int y1,int x2,int y2) { x1=(x1+3)%3;x2=(x2+3)%3; y1=(y1+3)%3;y2=(y2+3)%3; int u=x1*3+y1,v=x2*3+y2; mp[u][v]=1; } void pre() { int a1,a2,b1,b2; for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int k=0;k<4;k++) { a1=i+xx[k],b1=j+yy[k]; a2=a1+xx[k],b2=b1+yy[k]; if(a2+xx[k]<n&&b2+yy[k]<m)add(i,j,a2,b2); if(a2<n&&b2<m)add(i,j,a1,b1); } } int dfs(ll x) { if(x==ed)return 1; int a,b,a1,a2,b1,b2,t; if(q[x])t=q[x]; else t=q[x]=++sz; if(ans[t])return ans[t]; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { int t=i*3+j; if(x/bin[t]%11) for(int k=0;k<4;k++) { a1=(i+xx[k]+3)%3,b1=(j+yy[k]+3)%3; a2=(a1+xx[k]+3)%3,b2=(b1+yy[k]+3)%3; a=a1*3+b1,b=a2*3+b2; if((x/bin[a]%11)&&mp[t][a]) if(dfs(x-bin[t]-bin[a]+bin[b])==1)return ans[t]=1; if((x/bin[b]%11)&&mp[t][b]) if(dfs(x-bin[t]-bin[b]+bin[a])==1)return ans[t]=1; } } return ans[t]=-1; } int main() { //freopen("galaxy.in","r",stdin); //freopen("galaxy.out","w",stdout); bin[0]=1;for(int i=1;i<=10;i++)bin[i]=bin[i-1]*11; while(scanf("%d%d%d%d%d",&k,&n,&m,&xt,&yt)!=EOF) { q.clear();sz=bg=0; memset(ans,0,sizeof(ans)); memset(mp,0,sizeof(mp)); pre(); xt=(xt+2)%3;yt=(yt+2)%3;ed=bin[xt*3+yt]; int x,y,v; for(int i=1;i<=k;i++) { x=read();y=read(); x=(x+2)%3;y=(y+2)%3;v=x*3+y; bg+=bin[v]; } if(dfs(bg)==1)puts("Yes"); else puts("No"); } return 0; } |
Subscribe
计数器 9767858
OI 课件=>
OI 课件=>