Guarding the Chessboard

题意

Guarding the Chessboard - UVA 11214 - Virtual Judge ()

用最少的皇后占领标记的格子。

思路

暴力搜索。

1，枚举每个节点摆放情况，摆到目标个数就检查，检查合格就输出，不合格则增加摆放个数重新搜索。2，确定枚举上限。3，回溯不能一下子直接设置为0，要使用预先记录的值，横/纵/对角线/副对角线状态不一定一样。

#include <bits/stdc++.h>typedef long double ld;typedef long long ll;#define pb push_back#define mk make_pair#define mt make_tuple#define eb emplace_back#define pob pop_back#define rz resize#define mem(a,b) memset(a,b,sizeof(a))#define all(a) (a).begin(),(a).end()#define rall(a) (a).rbegin(),(a).rend()#define debug(a) cout<<#a<<"="<<a<<endl;#define xx first#define yy second#define qwe(i,a,b) for(int i=a;i<=b;i++)#define ewq(i,a,b) for(int i=a;i>=b;i--)inline ll rr(){ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}using namespace std;const int INF=0x3f3f3f3f;const ll mod[2]={int(1e9 + 7), 10007};const int base[2]={29,31};const int maxn=2e2+6;int n,m;int qr[maxn],qc[maxn],qrp[maxn],qrd[maxn];string s[maxn];int cnt,_;bool dfs(int x,int num) {if(num==cnt) {qwe(i,0,n-1)qwe(j,0,m-1)if(s[i][j]=='X'&& !qr[i]&& !qc[j]&& !qrp[i+j]&& !qrd[j-i+m]) return 0;return 1;}for(int i=x;i<n;i++) {for(int j=0;j<m;j++){int r=qr[i],c=qc[j],rp=qrp[i+j],rd=qrd[j-i+m];qr[i]=qc[j]=qrp[i+j]=qrd[j-i+m]=1;if(dfs(x+1,num+1)) return 1;qr[i]=r,qc[j]=c,qrp[i+j]=rp,qrd[j-i+m]=rd;}}return 0;}int main(int argc, char const *argv[]) {// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while (~scanf("%d",&n) && n) {scanf("%d",&m);for(int i=0;i<n;i++) {cin>>s[i];}for(cnt=0;cnt<=5;cnt++) {if(dfs(0,0)) {mem(qr,0),mem(qc,0),mem(qrp,0),mem(qrd,0);std::cout <<"Case "<< ++_ <<": "<<cnt<< '\n';break;}}}return 0;}

如果觉得《Guarding the Chessboard(暴力搜索)》对你有帮助，请点赞、收藏，并留下你的观点哦！