题目描述
B-4 方格填数 分数 20 作者 陈越 单位 浙江大学2014 年哈佛-麻省理工数学竞赛中一道题是这样的：将正整数 1, 2, ..., 64 填入 8×8 的方格棋盘中，使得对任何 1≤i<64，i 和 i+1 都必须填在两个具有公共边的方格中。求棋盘上对角线中所填数的和的最大值。（注意：两个对角线都要考虑；64 和1 也必须填在两个具有公共边的方格中。）
这题有点难…… 幸好我们并不要求你写程序解决这个问题。
你的任务是：对任一给定的数字填充方案，判定其是否满足填充的条件，并且在所有给出的方案中，找出满足条件的、且对角线数字和最大的那个方案。
输入格式：
输入在一行中首先给出两个正整数 n（≤100） 和 m（≤20），分别为棋盘的规模（即棋盘有 n×n 个方格）和输入的方案数量。因为容易证明奇数 n 一定不存在满足条件的解，所以题目保证给出的 n 都是偶数。
随后给出 m 个填充方案，每个方案占 n 行，每行 n 个不超过 n2 的数字。同行数字间以空格分隔。
输出格式：
在一行中首先输出满足条件的、且对角线数字和最大的方案数。随后一行中按照递增序输出这些方案的编号（编号按输入的顺序从 1 到 m）。
注意每行数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
4 5
16 1 2 3
15 14 13 4
10 11 12 5
9 8 7 6
16 1 2 3
15 14 13 4
10 11 12 5
9 8 7 10
15 16 1 2
14 13 4 3
11 12 5 6
10 9 8 7
3 4 5 6
2 13 12 7
1 14 11 8
16 15 10 9
10 5 4 3
7 12 13 2
8 11 14 1
9 6 15 16
输出样例：
2
1 4
代码:
// 20:01 ~ 20:16
// 好像忘记判断是否满足条件了
//== > 19 / 20
// dfs 判断一下,byd，测力4格式错误
#include <iostream>
#include <vector>
using namespace std;
const int N = 105;
int n,m;
int A[N][N];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool bfs(int h,int l,int val){
int tag = 0;
if(val == n * n)
val = 0;
for(int i=0;i<=3;i++){
int x = dir[i][0] + h;
int y = dir[i][1] + l;
if(x >= 1 && x <= n && y >= 1 && y <= n){
if(A[x][y] == (val+1) ){
tag = 1;
if(val == 0) return 1;
return bfs(x,y,val+1) & tag;
}
}
}
return tag;
}
bool check(int row,int con){
return bfs(row,con,1);
}
int main(){
cin >> n >> m;
vector<pair<int,int>> ve;
int mx = -0x7fffffff;
for(int z = 1;z<=m;z++){
int row=-1,con=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> A[i][j];
if(A[i][j] == 1){
row = i;
con = j;
}
}
}
// 判断是否满足条件
if(!check(row,con)) {
continue;
}
// 求对角线元素
int sum1 = 0;
int sum2 = 0;
for(int i=1;i<=n;i++){
sum1 += A[i][i];
sum2 += A[i][n-i+1];
}
int sum = max(sum1,sum2);
ve.push_back(make_pair(z,sum));
if(sum > mx) mx = sum;
}
vector <int> v;
for(int i=0;i<ve.size();i++){
if(ve[i].second == mx){
v.push_back(ve[i].first);
}
}
if(v.size() == 0){
cout << "0";
return 0;
}
cout << v.size() <<endl;
int ans = 0;
for(auto i : v){
if(ans != 0)
cout << " " << i;
else cout << i;
ans ++;
}
return 0;
}
奇怪的测试点
案例四显示格式错误，也不知道哪错了
标签：10,13,PAT,16,int,15,填数,2023,20 From： https://www.cnblogs.com/lordtianqiyi/p/18091728