一共2^15个状态
比较简单
/*
2^15 states
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std; const int maxn = ;
const int inf = ;
const int dx[]={,,,-,,-,,-};
const int dy[]={,-,,,-,,,-};
char mat[ ][ ];
struct Node{
int x,y;
char ch;
bool flag;
}node[ ];
int vis[ ]; bool in( int x,int y,int n,int m ){
if( x>=&&x<n&&y>=&&y<m ) return true;
else return false;
} bool ok_k( int x,int y,int n,int m ){
for( int i=;i<;i++ ){
int tx = x+dx[i];
int ty = y+dy[i];
if( in(tx,ty,n,m)==true ) {
if( mat[tx][ty]!='E' )
return false;
}
}
return true;
}
bool ok_q( int x,int y,int n,int m ){
for( int i=;i<=;i++ ){
for( int k=;k<;k++ ){
int tx = x+i*dx[k];
int ty = y+i*dy[k];
if( in(tx,ty,n,m)==true ){
if( mat[tx][ty]!='E' )
return false;
}
}
}
return true;
}
bool ok_b( int x,int y,int n,int m ){
for( int i=;i<=;i++ ){
for( int k=;k<;k++ ){
int tx = x+i*dx[k];
int ty = y+i*dy[k];
if( in(tx,ty,n,m)==true ){
if( mat[tx][ty]!='E' )
return false;
}
}
}
return true;
}
bool ok_r( int x,int y,int n,int m ){
for( int i=;i<=;i++ ){
for( int k=;k<;k++ ){
int tx = x+i*dx[k];
int ty = y+i*dy[k];
if( in(tx,ty,n,m)==true ){
if( mat[tx][ty]!='E' )
return false;
}
}
}
return true;
}
bool ok_n( int x,int y,int cnt_node ){
for( int i=;i<cnt_node;i++ ){
if( node[i].x==x&&node[i].y==y ) continue;
if( node[i].flag==false ) continue;
int ddx = abs( x-node[i].x );
int ddy = abs( y-node[i].y );
if( (ddx==&&ddy==)||(ddx==&&ddy==) )
return false;
}
return true;
} void re( int cnt_node ){
for( int i=;i<cnt_node;i++ ){
if( vis[ i ]== ){
mat[ node[i].x ][ node[i].y ] = node[i].ch;
node[ i ].flag = true;
}
}
} bool judge( int cnt_node,int n,int m ){
for( int i=;i<cnt_node;i++ ){
if( vis[ i ]== ){
mat[ node[i].x ][ node[i].y ] = 'E';
node[ i ].flag = false;
}
}
bool flag = true;
for( int i=;i<n;i++ ){
for( int j=;j<m;j++ ){
if( mat[i][j]=='E' )
continue;
if( mat[i][j]=='N'&&ok_n( i,j,cnt_node )==false ){
flag = false;
break;
}
else if( mat[i][j]=='R'&&ok_r( i,j,n,m )==false ){
flag = false;
break;
}
else if( mat[i][j]=='B'&&ok_b( i,j,n,m )==false ){
flag = false;
break;
}
else if( mat[i][j]=='Q'&&ok_q( i,j,n,m )==false ){
flag = false;
break;
}
else if( mat[i][j]=='K'&&ok_k( i,j,n,m )==false ){
flag = false;
break;
}
}
if( flag==false ) break;
}
re( cnt_node );
return flag;
} int main(){
char s[ ];
while( scanf("%s",&s)!=EOF ){
int n,m;
int cnt_node = ;
scanf("%d%d",&m,&n);
for( int i=;i<n;i++ ){
for( int j=;j<m;j++ ){
scanf("%s",s);
mat[i][j] = s[];
if( s[]!='E' ){
node[ cnt_node ].x = i;
node[ cnt_node ].y = j;
node[ cnt_node ].flag = true;
node[ cnt_node++ ].ch = s[];
}
}
}
scanf("%s",s);
int N = (<<cnt_node);
//printf("cnt_node=%d\n",cnt_node);
int ans = inf;
for( int i=;i<N;i++ ){
int temp_ans = ;
for( int j=;j<cnt_node;j++ ){
if( i&(<<j) ) {vis[ j ] = ,temp_ans++;}
else vis[ j ] = ;
}
if( judge( cnt_node,n,m )==true ){
ans = min( ans,temp_ans );
}
}
printf("Minimum Number of Pieces to be removed: %d\n",ans);
}
return ;
}