node.js 测试用例 Mxnet cocoa 后台管理系统模板 找公司做网站 hadoop源码 mysql操作日志 mysql获取当前时间戳 手动安装fastboot驱动 python算法 python中for循环的用法 python定义一个变量 python中re模块 python环境变量配置 java中instanceof java遍历list集合 java接口规范 php项目实例 kafka中文教程 计算机电子书 灼热峡谷 props 万能低格工具 零基础学python dvwa安装教程 快点蛆虫成就单刷 1660ti js延迟加载 c4dr19 抖音代码 微信临时链接多久失效 求字符串长度 c语言从入门到精通 逗号的作用 脚本大师 黑道圣徒4去马赛克 flushdns linux解压 冬青黑体简体中文
当前位置: 首页 > 学习教程  > 编程语言

P1219 [USACO1.5]八皇后 Checker Challenge

2020/12/28 19:06:29 文章标签:

P1219 [USACO1.5]八皇后Checker Challengee ---------------洛谷题目链接--------------- https://www.luogu.com.cn/problem/P1219 思路: 如何满足题目要求(已放棋子的行、列、对角线上不能再放其他棋子)? (1&#…

P1219 [USACO1.5]八皇后Checker Challengee

---------------洛谷题目链接---------------
https://www.luogu.com.cn/problem/P1219

思路:
如何满足题目要求(已放棋子的行、列、对角线上不能再放其他棋子)?
(1)、按顺序在每一行上放一颗棋子,这样的话保证在行上不会出现不满足题意的情况。
(2)、每次放棋子前判断列和对角线是否已经存在棋子:
<1>:循环判断将要放的棋子的所在列是否已有棋子,即queen[row - i - 1][col] == 1。
<2>:循环判断将要放的棋子所在的对角线是否有棋子,即queen[row - i - 1][col - i - 1] == 1(主对角线)、queen[row - i - 1][col + i + 1] == 1(副对角线),同时要保证列在棋盘中(col - i - 1 >= 0、col + i + 1 <= n - 1)

下面是一气呵成写出来的代码,但很可惜最后一个测试点超时了:

#include<iostream>
#include<cstring>
using namespace std;
int cnt = 0,n;
int queen[15][15]; 
void print() { //打印皇后的位置
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (queen[i][j] == 1) {
				printf("%d", j+1);
				if (i != n - 1) printf(" ");
				else putchar(10);
			}
			
		}
	}
}
bool check(int row, int col) {
	for (int i = 0; i < row; i++) {
			if (queen[row-i-1][col] == 1 || (col - i - 1>=0 && queen[row - i - 1][col - i - 1] == 1) || (col + i + 1 <= n-1 && queen[row - i - 1][col + i + 1] == 1)) {
			return false;//检查列、主对角、副对角
		}
	}
	return true;
}
void dfs(int row) {
	if (row == n) {
		cnt++;
		if (cnt <= 3) print();
		return;
	}
	for (int col = 0; col < n; col++) {
		if (check(row, col)) {
			queen[row][col] = 1;
			dfs(row + 1);
			queen[row][col] = 0;
		}
	}
}
int main() {
	memset(queen, 0, sizeof(queen));
	cin >> n;
	dfs(0);
	cout <<cnt << "\n";
	return 0;
}

难受,但又不想对代码进行大改,“冥思苦想”后想出来一个不太聪明的办法:
定义一个judge数组用来标记这一列之前是否已经放过棋子了,这样就可以一定程度上避免check()函数的for循环提高效率,最终勉强AC。
小改后的代码:

#include<iostream>
#include<cstring>
using namespace std;
int cnt = 0;
int queen[15][15]; 
int judge[15];
int n;
void print() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (queen[i][j] == 1) {
				printf("%d", j + 1);
				if (i != n - 1) printf(" ");
				else putchar(10);
			}
		}
	}
}
bool check(int row, int col) {
	for (int i = 0; i < row; i++) {
		if (queen[row - i - 1][col] == 1 || (col - i - 1 >= 0 && queen[row - i - 1][col - i - 1] == 1) || (col + i + 1 <= n - 1 && queen[row - i - 1][col + i + 1] == 1))//列、主对角、副对角
			return false;//不满足情况返回false
	}
	return true;
}
void dfs(int row) {
	if (row == n) {//如果n颗棋子都放完了说明方法可行
		cnt++;
		if (cnt <= 3) print();//打印前三种答案
		return;
	}
	for (int col = 0; col < n; col++) {
		if (judge[col]&&check(row, col)) {//先看看这一列之前已经放过棋子了,减少调用check()函数的次数
			queen[row][col] = 1;
			judge[col] = 0;
			dfs(row + 1);
			judge[col] = 1;//回溯
			queen[row][col] = 0;
		}
	}
}
int main() {
	memset(queen, 0, sizeof(queen));
	memset(judge, 1, sizeof(judge));
	cin >> n;
	dfs(0);//从第零行开始放棋子
	cout <<cnt << "\n";
	return 0;
}

完事儿。


本文链接: http://www.dtmao.cc/news_show_550166.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?