UVA 11214 Guarding the Chessboard(回溯)

分手后的思念是犯贱 2024-02-17 19:12 50阅读 0赞

题意：类似n皇后问题，要求用最少的皇后防守所有的X;

思路：暴力回溯，开始一直按照n皇后的思路来解（即同行同列同对角线不能有多个皇后，但事实证明本题可以，因为是逐行向下搜索，所以同行上没有多个皇后）

AC代码如下：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=10+2;
    char g[maxn][maxn];
    int vis[4][2*maxn];
    int n,m;
    bool check(){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			if(g[i][j]=='X'){
    				if(!vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+maxn])
    				return false ;
    			}
    		}
    	}
    	return true;
    }
    bool dfs(int num,int row,int c){  //num表示皇后的个数，row表当前行，c表示放置了多少个皇后 
    	if(c==num){
    		int flag=check();
    		if(flag)return true;
    		else return false;
    	}
    	for(int i=row;i<n;i++){
    		for(int j=0;j<m;j++){
    			int a1,a2,a3,a4;      //分别保存原来的值 
    		        a1=vis[0][i] ,a2=vis[1][j] ,a3=vis[2][i+j] ,a4=vis[3][i-j+maxn]	;
    				vis[0][i]=1;vis[1][j]=1;
    				vis[2][i+j]=1;vis[3][i-j+maxn]=1;
    				if(dfs(num,row+1,c+1))return true;
    				vis[0][i]=a1;vis[1][j]=a2;
    				vis[2][i+j]=a3;vis[3][i-j+maxn]=a4;
    		}
    	}
    	return false;
    }
    int main(){
    	int count1=0;
    	while(scanf("%d%d",&n,&m)==2 && n){
    		for(int i=0;i<n;i++)scanf("%s",g[i]);
    		memset(vis,0,sizeof(vis));
    		for(int i=0;i<=n;i++){
    			if(dfs(i,0,0)){
    				printf("Case %d: %d\n",++count1,i);
    				break;
    			}
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 11214 Guarding the Chessboard(回溯)

题意：类似n皇后问题，要求用最少的皇后防守所有的X; 思路：暴力回溯，开始一直按照n皇后的思路来解（即同行同列同对角线不能有多个皇后，但事实证明本题可以，因为是逐行向下搜索，

分手后的思念是犯贱/ 2024年02月17日 19:12/ 0 赞/ 51 阅读

相关 UVA 208 Firetruck 消防车（回溯 + 剪枝）

题意：一个包含<=20个结点的无向图，输入一个结点k，求从1到的k的所有路径，要求字典序输出，并且结点不能重复。思路：刚开始直接回溯，结果超时了；从终点出发，找到所有与终点

迷南。/ 2024年02月17日 19:12/ 0 赞/ 9 阅读

相关【UVa#10325】The Lottery

Description [UVa\10325][UVa_10325] 给定n和m个数，求1~n中不被这m个数中任意一个数整除的数的个数 Solution 容斥原

青旅半醒/ 2023年06月05日 08:54/ 0 赞/ 25 阅读

相关 UVA11752 The Super Powers

最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。这道题是很久前做的，细节记不太清了。。。

深藏阁楼爱情的钟/ 2022年09月20日 12:44/ 0 赞/ 28 阅读

相关 uva 1623——Enter The Dragon

题意：有n个装满水的湖，可以预知将来m天下雨情况，每次下满一个湖，或者不下，不下雨的时候可以让某个湖变干，问是否存在一种方案使得每次下雨之前湖总是干的。思路：贪心

以你之姓@/ 2022年08月09日 16:42/ 0 赞/ 167 阅读

相关 uva 1614——UVA 1614 - Hell on the Markets

Description [![Download as PDF][]][Download as PDF 1]Most financial institutions had be

客官°小女子只卖身不卖艺/ 2022年08月09日 14:56/ 0 赞/ 127 阅读

相关 UVA 11300 Spreading the Wealth

![Center][] include <cstdio> include <cmath> include <algorithm>

Dear 丶/ 2022年08月07日 02:38/ 0 赞/ 188 阅读

相关 uva 10254——The Priest Mathematician

题意：汉诺塔题目的变形，有4根柱子，可以把顶部的k个盘子移到最后的柱子上，然后按照汉诺塔，问最后走的最小步数。思路：递推，经过递推可以发现f\[n\] = f\[

ゝ一纸荒年。/ 2022年07月28日 01:35/ 0 赞/ 31 阅读

相关找规律-CodeForces 1027B-Numbers on the Chessboard

找规律-CodeForces 1027B-Numbers on the Chessboard -------------------- 题目链接：

客官°小女子只卖身不卖艺/ 2022年05月15日 11:59/ 0 赞/ 199 阅读

相关 uva 701 - The Archeologists' Dilemma

[题目链接：uva 701 - The Archeologists' Dilemma][uva 701 - The Archeologists_ Dilemma]

待我称王封你为后i/ 2022年05月12日 23:28/ 0 赞/ 145 阅读