【题目】洛谷10月月赛R1 提高组

【题意】给定n*n棋盘和<=16个棋子，给几个棋子种类和攻击范围，现我方只有一马，求能否吃王。

【算法】状压+BFS

【题解】16种棋子中，马不能吃马，直接处理马和王，那么就剩13个棋子，可以压成2^13表示棋盘现有棋子存活状态。

然后对vis[2^13][n][n]进行bfs。

细节：

1.攻击直到碰到其它棋子，那个碰到的棋子也算攻击范围内。

2.判断碰到棋子时，注意该棋子是否在当前局面存活。

3.多组数据，Q中途退出要清空。

学到了：

1.一份长代码要细心经营，视若珍宝，动键盘之前要冷静把思路和框架理清楚，过程中步步为营，慢慢写总能写完的。

2.不要轻易相信自己的代码没有bug了，尽量对拍，把小数据的中间结果输出和手算比较正确性，从而改掉尽可能多的错误。

3.不要害怕写长的复杂的代码，先做框架，然后一步一步把子过程做好，一份超长代码就慢慢构造出来了。

4.枚举对角线的姿势！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int inf=0x3f3f3f3f,maxn=60;int n,mp[1<<14][maxn][maxn],map[maxn][maxn],p[maxn][maxn],ans;int cnt,tot,Tx,Ty,Sx,Sy;bool vis[1<<14][maxn][maxn];struct Node{
    int x,y;}c[15],ch[15];struct cyc{
    int S,x,y,st;};queue
           
            Q;void qishi(int S,int x,int y){ mp[S][x-1][y+2]=mp[S][x+1][y+2]=mp[S][x+2][y-1]=mp[S][x+2][y+1]=1; if(x-2>0)mp[S][x-2][y-1]=mp[S][x-2][y+1]=1; if(y-2>0)mp[S][x-1][y-2]=mp[S][x+1][y-2]=1;}void king(int S,int x,int y){ mp[S][x-1][y-1]=mp[S][x-1][y]=mp[S][x-1][y+1]=1; mp[S][x][y-1]=mp[S][x][y+1]=1; mp[S][x+1][y-1]=mp[S][x+1][y]=mp[S][x+1][y+1]=1;}bool m(int S,int x,int y){ if(map[x][y]<=1)return 1; if(map[x][y]==2||map[x][y]==7)return 0; if(S&(1<<(p[x][y]-1)))return 0; return 1;}void chengbao(int S,int x,int y){ for(int i=x-1;i>=1;i--)if(m(S,i,y))mp[S][i][y]=1;else{mp[S][i][y]=1;break;} for(int i=x+1;i<=n;i++)if(m(S,i,y))mp[S][i][y]=1;else{mp[S][i][y]=1;break;} for(int i=y-1;i>=1;i--)if(m(S,x,i))mp[S][x][i]=1;else{mp[S][x][i]=1;break;} for(int i=y+1;i<=n;i++)if(m(S,x,i))mp[S][x][i]=1;else{mp[S][x][i]=1;break;}}void zhujiao(int S,int x,int y){ for(int i=1;i
            
             n||y<1||y>n||mp[S][x][y]||vis[S][x][y])return; vis[S][x][y]=1; if(map[x][y]==2)ans=st; if(map[x][y]>=3&&map[x][y]<=6)if(S&(1<<(p[x][y]-1)))S^=(1<<(p[x][y]-1)); vis[S][x][y]=1; Q.push((cyc){S,x,y,st});}char s[maxn];int main(){while(scanf("%d",&n)==1){ cnt=tot=0; memset(map,0,sizeof(map));memset(p,0,sizeof(p));memset(mp,0,sizeof(mp));memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=n;j++){ if(s[j]=='K')map[i][j]=7,c[++cnt].x=i,c[cnt].y=j; if(s[j]=='X')map[i][j]=2,Tx=i,Ty=j,c[++cnt].x=i,c[cnt].y=j; if(s[j]=='O')Sx=i,Sy=j; if(s[j]=='C')map[i][j]=3,ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++; if(s[j]=='B')map[i][j]=4,ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++; if(s[j]=='Q')map[i][j]=5,ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++; if(s[j]=='P')map[i][j]=6,ch[tot].x=i,ch[tot].y=j,p[i][j]=tot++; } } for(int S=0;S<(1<