/*
推荐题型:四星,没有解出。。。
带权值的八皇后问题
思路:按行进行搜索,数组p记录每行皇后所在列。
每次搜索到第八行,进行一次处理即可。
*/
#include <cstdio>
#include <cstring>
int G[10][10];
int a[10],b[10],c[20];
int p[10];
int ans;
void dfs(int cur)
{
if(cur==8)
{
int num=0;
for(int i=0;i<8;i++)
num+=G[i][p[i]];
if(num>ans)
ans=num;
}
//int ok=
for(int i=0;i<8;i++)
{
if(!a[i] && !b[cur+i] && !c[cur-i+8])
{
p[cur]=i;
a[i]=b[cur+i]=c[cur-i+8]=1;
dfs(cur+1);
a[i]=b[cur+i]=c[cur-i+8]=0;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
int k;
scanf("%d",&k);
while(k--)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
scanf("%d",&G[i][j]);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
ans=0;
dfs(0);
printf("%5d\n",ans);
}
return 0;
}
/*
错解
*/
#include <cstdio>
#include <cstring>
const int nMax=8;
int G[nMax][nMax];
bool visit[nMax][nMax];
int a[nMax],b[nMax],c[2*nMax],d[2*nMax];
int ans;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool check(int x,int y)
{
if(x<0 || x>=nMax || y<0 || y>=nMax)
return false;
if(visit[x][y])
return false;
if(a[x] || b[y] || c[x-y+nMax] || d[x+y])
return false;
return true;
}
void dfs(int x,int y,int sum,int n)
{
visit[x][y]=1;
if(n>nMax)
{
if(sum>ans)
ans=sum;
return;
}
a[x]=1;
b[y]=1;
c[x-y+nMax]=1;
d[x+y]=1;
for(int i=0;i<4;i++)
{
int xx,yy;
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy))
dfs(xx,yy,sum+G[x][y],n+1);
}
a[x]=0;
b[y]=0;
c[x-y+nMax]=0;
d[x+y]=0;
for(int i=0;i<4;i++)
{
int xx,yy;
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy))
dfs(xx,yy,sum,n);
}
visit[x][y]=0;
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
int k;
scanf("%d",&k);
while(k--)
{
memset(G,0,sizeof(G));
memset(visit,0,sizeof(visit));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int i=0;i<nMax;i++)
for(int j=0;j<nMax;j++)
scanf("%d",&G[i][j]);//漏掉了地址符&
dfs(0,0,0,0);
printf("%5d\n",ans);
}
return 0;
}
分享到:
相关推荐
使用此脚本,您可以生成一组有关地球上任何位置在不同时刻的太阳方位角位置的数据。 该数据可用于许多应用,例如确定任何平面从真北的方位角的方向。 语法是“sun_azimuth_data”(无... 与脚本的示例交互: *-*-*-*
资源分类:Python库 所属语言:Python 资源全名:sultan-0.3.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
SULTAN-4TH-JUNE
sultan-kernel-celox:适用于Samsung Skyrocket(SGH-I727)和Samsung Hercules(SGH-T989)的AOSP内核,基于官方的Samsung Jelly Bean内核源代码发布,并重新基于CAF jb_1.9.6
SpringPetClinic样品申请 通过一些图表了解Spring Petclinic应用程序 在本地运行诊所 Petclinic是使用构建的应用程序。 您可以构建一个jar文件并从命令行运行它: ...cd spring-petclinic ./mvnw package ...
Sultan POS的主要目标是小型市场,并且能够在Raspberry Pi上运行。特征联网(使用websocket) 多价项目类别供应商多用户和权限数据库SQLite / MySQL 销售报告物品销售报告资金报告使用平均值计算保证金客户资料库...
资源分类:Python库 所属语言:Python 资源全名:sultan-0.3.1-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
苏丹-后-办公室-html-模板
杰里科(Wadi Al-Qalt,Ain或Tal Sultan和Al-Nwehmeh)和拉马拉(Safa,Turmus Aya和Qibia)。 由于没有对这些地区进行分类研究,因此我们对巴勒斯坦的400个采样菌群进行了统计处理。 此外,分类是根据1979年的...
餐厅项目 Sultan是使用Bootstrap构建的动态,适合移动设备的Web应用程序。 用户可以检查菜单并在线订购希腊食品。 灵感来自我梦想有一天开设自己的餐厅。
我们的堆栈技术:JavaFX + OracleSQL数据集我们已经浏览了100个数据集,并选择了Nur-sultan(Astana)的房价,因为首先它是关于我们的国家的信息,并且它是一个非常有用的数据集,包含许多有用的列。 表结构: id...
马来西亚霹雳州Pendidikan Sultan Idris Universiti Pendidikan Sultan Idris的Aplikasi Chrome Tab untuk staf dan pelajar。 马来西亚霹雳州Pendidikan Sultan Idris的Aplikasi Chrome Tab untuk kegunaan staf ...
其中包括al-amin,karkun,sultan-jdt,tun-mahadir 马来语MVC,尤其是文件夹名称,类和变量。 在应用程序文件夹中,有4个主要文件夹,即控件,显示,库,询问控件=>控制器,显示=>视图,书=>库和询问=>模型。 ...
人口由马来西亚霹雳州SMK Sultan Tajul Ariffin Manong的中一至中二学生组成。 研究的设计是使用调查方法完成的。 对这些学生进行了问卷调查,以评估他们对YouTube在英语学习和自主学习中的使用的看法。 SPSS用于...
Good hand written notes of our Prof.Ahmed Sultan about Discrete Fourier Transform
作者:Sultan Alam,IEEE的学生会员,Satyajit Thakor,IEEE的高级会员和Syed Abbas 共有三个目录:1)熵向量和相关分布-第三节,2)内边界-第四节,3)网络编码-第五节。在以上三个目录中,我们都有第三节中给出的...
合并 2020 年 3 月安全补丁 (9.0.0 最终版) 包含所有先前更新 合并 2020 年 1 月安全补丁 (9.0.0) 包含所有先前更新 合并 9 月安全补丁 (9.0.0_r48) 添加 4K 相机 (Sultan Hal) 改进相机快照索尼相机补丁 新的和改进...
该项目旨在回答以下问题:给定状态A和状态B下的抽样,如何通过增强的抽样框架来选择能够在它们之间进行转换的一些集体变量。 我们认为,来自任何可区分的有监督机器学习算法的决策函数都代表了良好的起始简历。 此...
德维乔托莫 1、莫哈末阿齐兹·阿卜杜勒·拉赫曼 1、莫哈末哈达·穆罕默德·阿里夫 1、海里·扎姆祖里 2 和万·穆赫德·哈菲兹·万·阿兹里 2马来西亚工艺大学先进车辆系统研究小组,54100 Jalan Sultan Yahya Petra...