TLE，额 ，有空再写吧。
#include<queue> #include<cstdio> #include<vector> #include<algorithm> #include<cmath> using namespace std; const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1}; const int N = 80; struct node{ int x,y; int step,state; }; queue<node>q; int n,sx,sy; char a[N][N]; int id[N][N],tot; bool Vis[N][N][20000]; bool check( int state,int x ,int y) { if(Vis[x][y][state]) return 0; //下 for(int i=x+1;i<=n;i++) if(a[i][y]!='.'&& !(state&(1<<id[x][y]))) { if(a[i][y]=='C'||a[i][y]=='Q') return 0; break; } //上 for(int i=x-1;i<=1;i--) if(a[i][y]!='.'&& !(state&(1<<id[i][y]))) { if(a[i][y]=='C'||a[i][y]=='Q') return 0; break; } //左 for(int j=y+1;j<=n;j++) if(a[x][j]!='.'&&!(state&(1<<id[x][j]))) { if(a[x][j]=='C'||a[x][j]=='Q') return 0; break; } //右 for(int j=y-1;j>=1;j--) if(a[x][j]!='.'&&!(state&(1<<id[x][j]))) { if(a[x][j]=='C'||a[x][j]=='Q') return 0; break; } //左上 for(int i=x-1,j=y-1;i>=1&&j>=1;i--,j--) if(a[i][j]!='.'&&!(state&(1<<id[i][j]))) { if(a[i][j]=='B'||a[i][j]=='Q') return 0; break; } //右上 for(int i=x+1,j=y-1;i<=n&&j>=1;i++,j--) if(a[i][j]!='.'&&!(state&(1<<id[i][j]))) { if(a[i][j]=='B'||a[i][j]=='Q') return 0; break; } //左下 for(int i=x-1,j=y+1;i>=1&&j<=n;i--,j++) if(a[i][j]!='.'&&!(state&(1<<id[i][j]))) { if(a[i][j]=='B'||a[i][j]=='Q') return 0; break; } //右下 for(int i=x+1,j=y+1;i<=n&&j<=n;i++,j++) if(a[i][j]!='.'&&!(state&(1<<id[i][j]))) { if(a[i][j]=='B'||a[i][j]=='Q') return 0; break; } int X,Y; for(int i=0;i<=7;i++) { X=x+dx[i];Y=y+dy[i]; if(X>=1&&X<=n&&Y>=1&&Y<=n&&a[X][Y]=='K') return 0; } if(x!=1&&((y!=n&&a[x-1][y+1]=='P'&&!(state&(1<<(id[x-1][y+1]))||(y!=1&&a[x-1][y-1]=='P'&&!(state&(1<<id[x-1][y-1]))))))) return 0; for(int i=x-1;i<=x+1;i++) for(int j=y-1;j<=y+1;j++) if(x>=1&&x<=n&&y>=1&&y<=n) { if(a[i][j]=='X') return 0; } return 1; } void work() { queue<node>q;tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { id[i][j]=-1,a[i][j]=0; for(int k=0;k<=(1<<15);k++) Vis[i][j][k]=0; } for(int i=1;i<=n;i++) { scanf("%s",a[i]+1); for(int j=1;j<=n;j++) { if(a[i][j]=='O') sx=i,sy=j,a[i][j]='.'; else if(a[i][j]=='C'||a[i][j]=='K'||a[i][j]=='Q'||a[i][j]=='X'||a[i][j]=='P') id[i][j]=tot++; else a[i][j]='.'; } } if(!check(0,sx,sy)) { cout<<-1; return; } q.push((node){sx,sy,0,0}); node now;int x,y,state; while(!q.empty()) { now=q.front();q.pop(); state=now.state; for(int i=0;i<8;i++) { x=now.x+dx[i];y=now.y+dy[i]; if(x<1||x>n||y<1||y>n) continue; if(a[x][y]=='X') { printf("%d ",now.step+1); return; } if(a[x][y]!='.') state|= 1<<id[x][y]; if(check(state,x,y)) Vis[x][y][state]=1,q.push((node){x,y,now.step+1,state}); } } cout<<-1; } int main() { while(scanf("%d",&n)) work(); return 0; }