题目链接:
https://vjudge.net/problem/UVA-11214
题意:
给出m*n棋盘上的目标点，求最少用几个皇后可以守卫所有目标点。
题解:
类似八皇后做法，2维数组标记行、列、主对角线、副对角线。
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int n,m,maxd; 19 int tag[15][15]; 20 int vis[4][30]; 21 22 bool ok(){ 23 for(int i=0; i<n; i++) 24 for(int j=0; j<m; j++){ 25 if(tag[i][j] && !vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+n]) 26 return false; 27 } 28 return true; 29 } 30 31 bool dfs(int d,int cur){ 32 if(d == maxd){ 33 if(ok()) return true; 34 return false; 35 } 36 37 for(int pos=cur; pos<n*m; pos++){ 38 int r = pos/m, c = pos%m; 39 int t1 = vis[0][r], t2 = vis[1][c], t3 = vis[2][r+c], t4 = vis[3][r-c+n]; 40 vis[0][r] = vis[1][c] = vis[2][r+c] = vis[3][r-c+n] = 1; 41 if(dfs(d+1,pos+1)) return true; 42 vis[0][r]=t1, vis[1][c]=t2, vis[2][r+c]=t3, vis[3][r-c+n]=t4; 43 } 44 return false; 45 } 46 47 int main(){ 48 int cas = 0; 49 while(scanf("%d",&n) && n){ 50 scanf("%d",&m); 51 MS(tag); MS(vis); 52 char c; 53 for(int i=0; i<n; i++) 54 for(int j=0; j<m; j++){ 55 scanf(" %c",& c); 56 if(c == 'X'){ 57 tag[i][j] = 1; 58 } 59 } 60 61 for(maxd=1; ; maxd++){ 62 if(dfs(0,0)){ 63 printf("Case %d: %d ",++cas,maxd); 64 break; 65 } 66 } 67 } 68 69 return 0; 70 }