洛谷月赛八连测 SAC E#1 - 一道大水题 Knight

xiaoxiao2021-02-28  23

一开始一直re。。。。 原来是tot,cnt忘付出值为零了。。。。 跳了一上午。。 这个题就是一个包搜 因为只有16个旗子。 但白骑士,与黑骑士和国王不用记,因为你吃不掉黑骑士,国王你只要吃掉就赢了 所以将所有状态用二进制记录下来,有1<<13(2^13) 种,预处理出他们能走于不能走的地方 然后bfs从一个状态到另一个状态。

#include<cstdio> #include<cstdlib> #include<algorithm> #include<iostream> #include<queue> #include<cstring> #define ll long long using namespace std; struct st{ int x,y,s,k; }; int n;int p[60][60],cnt,tot;st ch[19],c[19]; int xx[10]={1,1,-1,-1,2,-2,2,-2},yy[10]={2,-2,2,-2,1,1,-1,-1}; int xx2[6]={1,1,-1,-1},yy2[6]={1,-1,1,-1}; char b[55][55];int sx,sy,tx,ty,a[55][55]; bool vis[1<<14][60][60]; bool check(int k,int x,int y){ //if(k&(1<<(p[x][y]-1))&&p[x][y]==tot-1) //printf("1"); if(a[x][y]<=1) return 1; if(a[x][y]==2||a[x][y]==7)return 0; if(k&(1<<(p[x][y]-1))) return 0; return 1; } void C(int k,int x,int y){ for(int i=x+1;i<=n;i++){ vis[k][i][y]=1; if(!check(k,i,y)) break; } for(int i=x-1;i>=1;i--){ vis[k][i][y]=1; if(!check(k,i,y)) break; } for(int i=y+1;i<=n;i++){ vis[k][x][i]=1; if(!check(k,x,i)) break; } for(int i=y-1;i>=1;i--){ vis[k][x][i]=1; //printf("%d %d\n",x,i); if(!check(k,x,i)) break; } } void K(int k,int x,int y){ for(int i=0;i<8;i++){ int dx=x+xx[i],dy=y+yy[i]; if(dx<1||dy<1||dx>n||dy>n) continue; vis[k][x+xx[i]][y+yy[i]]=1; } } void B(int k,int x,int y){ for(int i=0;i<4;i++){ int dx=x+xx2[i],dy=y+yy2[i]; while(dx<=n&&dx>=1&&dy<=n&&dy>=1&&check(k,dx,dy)){ //printf("%d %d\n",dx,dy); vis[k][dx][dy]=1;dx+=xx2[i],dy+=yy2[i]; } } } void X(int k,int x,int y){ for(int i=0;i<4;i++) { int dx=x+xx2[i],dy=y+yy2[i]; if(dx<1||dy<1||dx>n||dy>n) continue; vis[k][x+xx2[i]][y+yy2[i]]=1; } vis[k][x+1][y]=1;if(x-1>0)vis[k][x-1][y]=1;vis[k][x][y+1]=1;if(y-1>0)vis[k][x][y-1]=1; tx=x,ty=y; } void P(int k,int x,int y){ vis[k][x+1][y+1]=1;if(y-1>0)vis[k][x+1][y-1]=1; } queue <st> q; int bfs(){ while(!q.empty()){ st x=q.front();q.pop(); //printf("%d %d %d\n",x.x,x.y,x.s); for(int i=0;i<8;i++){ int qx=x.x+xx[i],qy=x.y+yy[i]; if(qx==tx&&qy==ty) { return x.s+1;} if(qx<1||qy<1||qx>n||qy>n) continue; if(vis[x.k][qx][qy]) continue; st tmp; tmp.k=x.k; if(a[qx][qy]>=3&&a[qx][qy]<=6) if(x.k&(1<<p[qx][qy]-1)) tmp.k=tmp.k^(1<<p[qx][qy]-1); tmp.x=qx,tmp.y=qy,tmp.s=x.s+1; q.push(tmp); vis[tmp.k][qx][qy]=1; } } return -1; } int main(){ while(scanf("%d",&n)!=EOF){ cnt=tot=0; memset(vis,0,sizeof vis); memset(a,0,sizeof a); memset(p,0,sizeof p); memset(b,0,sizeof b); for(int i=1;i<=n;i++) { cin>>b[i]+1; for(int j=1;j<=n;j++) { if(b[i][j]=='O') sx=i,sy=j; if(b[i][j]=='C') ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++,a[i][j]=3; if(b[i][j]=='K') c[++cnt].x=i,c[cnt].y=j,a[i][j]=7; if(b[i][j]=='B') ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++,a[i][j]=4; if(b[i][j]=='Q') ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++,a[i][j]=5; if(b[i][j]=='X') c[++cnt].x=i,c[cnt].y=j,tx=i,ty=j,a[i][j]=2; if(b[i][j]=='P') ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++,a[i][j]=6; }} for(int k=0;k<(1<<tot);k++){ for(int i=1;i<=cnt;i++) if(a[c[i].x][c[i].y]==2) X(k,c[i].x,c[i].y); else K(k,c[i].x,c[i].y); for(int i=0;i<tot;i++) if((1<<i)&k){ int tmp=a[ch[i].x][ch[i].y]; if(tmp==3) C(k,ch[i].x,ch[i].y); if(tmp==4) B(k,ch[i].x,ch[i].y); if(tmp==5) B(k,ch[i].x,ch[i].y),C(k,ch[i].x,ch[i].y); if(tmp==6) P(k,ch[i].x,ch[i].y); } vis[k][tx][ty]=0; } if(vis[(1<<tot)-1][sx][sy]){ printf("-1\n");continue; } while(!q.empty())q.pop(); q.push((st){sx,sy,0,(1<<tot)-1});vis[(1<<tot)-1][sx][sy]=1; printf("%d\n",bfs()); } }
转载请注明原文地址: https://www.6miu.com/read-1400035.html

最新回复(0)