The Sultan's Successors UVA - 167
the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one.) Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.) Input Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a positive integer less than 100. There will never be more than 20 boards. Output Output will consist of k numbers consisting of your k scores, each score on a line by itself and right justified in a field 5 characters wide.
Sample Input
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Sample Output
260
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int c[],vis[][],tot,n=,sum_max;
int mapn[][];
void search(int cur)
{
if(cur==n)//递归边界,只要走到了这里,所有皇后必然不冲突
{
if(sum_max<tot)
sum_max = tot;
}
else for(int i=;i<n;i++)
{
if(!vis[][i]&&!vis[][cur+i]&&!vis[][cur-i+n])//利用二维数组直接判断
{//0为竖行,1为副对角线,2为主对角线
c[cur] = i;//保存下每行皇后的位置
tot += mapn[cur][i];
vis[][i] = vis[][cur+i] = vis[][cur-i+n] = ;
search(cur+);
vis[][i] = vis[][cur+i] = vis[][cur-i+n] = ;//记得改回来
tot -= mapn[cur][i];
}
}
}
int main()
{
int T;
cin >> T;
while(T--)
{
sum_max = ,tot = ;
memset(vis,,sizeof(vis));
for(int i=;i<;i++)
for(int j=;j<;j++)
{
cin >> mapn[i][j];
}
search();
printf("%5d\n",sum_max);
}
return ;
}
最新文章
- js中的逻辑与(&;&;)和逻辑或(||)
- ASPX.Net控件
- 10G R2 参数文件相关
- 车脸检测 Adaboost 检测过程
- Unity Shaders Vertex &; Fragment Shader入门
- java开发--struts2 标签库使用
- #定位系统性能瓶颈# strace &;amp; ltrace
- labview 移位寄存器、隧道、索引隧道的区别
- PHP中的定界符格式
- Leetcode-34-Search Insert Position-(Medium)
- permutation求全排列
- bzoj千题计划177:bzoj1858: [Scoi2010]序列操作
- iOS.FBTweak
- python学习之老男孩python全栈第九期_day011知识点总结
- java 装饰设计模式模式
- Laravel中如何将单个routes.php分割成多个子文件
- leetcode561
- git merge后,后悔了如何回退
- Markdown_00_资源帖
- Linux实战教学笔记32:企业级Memcached服务应用实践