博星卓越 网站开发方案,有哪些网站可以做海报,公主岭市住房和城乡建设局网站,购物网站开发要解决的问题标题#xff1a;六角幻方 把 1 2 3 ... 19 共19个整数排列成六角形状#xff0c;如下#xff1a; * * * * * * * * * * * * * * * * * * * 要求每个直线上的数字之和必须相等。共有15条直线哦#xff01; 再给点线索吧#xff01;我们预先填好了2个数字…标题六角幻方 把 1 2 3 ... 19 共19个整数排列成六角形状如下 * * * * * * * * * * * * * * * * * * * 要求每个直线上的数字之和必须相等。共有15条直线哦 再给点线索吧我们预先填好了2个数字第一行的头两个数字是15 13参见图【p1.png】黄色一行为所求。 请你填写出中间一行的5个数字。数字间用空格分开。 这是一行用空格分开的整数请通过浏览器提交答案不要填写任何多余的内容比如说明性的文字等
解题报告 好久没写搜索了当个练习。
不难发现每一行的值的和应该是38所以我们已经有了三个已知数字了。
根据对称性把这三个数放在每一行的开始相当于有了三个已知行的行首然后按行dfs同时判断是否凑够了38如果超了38那就直接return就行这一点可以用附初始值为比较大的值这里用了100000来实现。如果还没填满这一行但是和已经大于38了 或者 都填满了并且还不是38那就return。这应该是最优秀的剪枝了是每一步都会有剪枝。当然如果不这样剪枝而是直接 每一行都填满了再判断是否等于38也可以。
最终答案
10 12 16 13 4 2 19 15 8 5 7 3 14 6 1 17 9 11 18
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
int a[55][55],all[55] {0,10,13,15,0,0};
int up[55] {0,3,4,5,4,3};
bool vis[55],ok[55][55];
bool cc() {if(a[1][2]a[2][2]a[3][2]a[4][1]!38) return 0;if(a[1][3]a[2][3]a[3][3]a[4][2]a[5][1]!38) return 0;if(a[2][4]a[3][4]a[4][3]a[5][2]!38) return 0;if(a[3][5]a[4][4]a[5][3]!38) return 0;if(a[1][3]a[2][4]a[3][5]!38) return 0;if(a[1][2]a[2][3]a[3][4]a[4][4]!38) return 0;if(a[1][1]a[2][2]a[3][3]a[4][3]a[5][3]!38) return 0;if(a[2][1]a[3][2]a[4][2]a[5][2]!38) return 0;if(a[3][1]a[4][1]a[5][1]!38) return 0;return 1;
}
bool check() {if(a[1][2]a[2][2]a[3][2]a[4][1]!38 a[1][2]a[2][2]a[3][2]a[4][1]100000) return 0;if(a[1][3]a[2][3]a[3][3]a[4][2]a[5][1]!38 a[1][3]a[2][3]a[3][3]a[4][2]a[5][1]100000) return 0;if(a[2][4]a[3][4]a[4][3]a[5][2]!38 a[2][4]a[3][4]a[4][3]a[5][2]100000) return 0;if(a[3][5]a[4][4]a[5][3]!38 a[3][5]a[4][2]a[5][3]100000) return 0;if(a[1][3]a[2][4]a[3][5]!38 a[1][3]a[2][4]a[3][5]100000) return 0;if(a[1][2]a[2][3]a[3][4]a[4][4]!38 a[1][2]a[2][3]a[3][4]a[4][4]100000) return 0;if(a[1][1]a[2][2]a[3][3]a[4][3]a[5][3]!38 a[1][1]a[2][2]a[3][3]a[4][3]a[5][3]100000) return 0;if(a[2][1]a[3][2]a[4][2]a[5][2]!38 a[2][1]a[3][2]a[4][2]a[5][2]100000) return 0;if(a[3][1]a[4][1]a[5][1]!38 a[3][1]a[4][1]a[5][1]100000) return 0; return 1;
}
void dfs(int x,int y) {if(x 6) {if(cc() 0) return;for(int i 1; i5; i) {for(int j 1; jup[i]; j) {printf(%d ,a[i][j]);}printf(\n);}return; }if(check() 0) return;if(ok[x][y]) {dfs(x,y1);return;}for(int i 1; i19; i) {if(vis[i]) continue;if(all[x] i 38) continue;if(y up[x]) {if(all[x] i ! 38) continue;else {all[x] i;vis[i] 1;a[x][y] i;dfs(x1,1);a[x][y] 100000;all[x] - i;vis[i] 0;return;}}vis[i] 1;all[x] i;a[x][y] i;dfs(x,y1);a[x][y] 100000;vis[i] 0;all[x] - i;}
}
int main()
{for(int i 1; i5; i) {for(int j 1; j5; j) a[i][j] 100000;}a[1][1]10;a[2][1]13;a[3][1]15;ok[1][1]1;ok[2][1]1;ok[3][1]1;vis[10]1;vis[13]1;vis[15]1;dfs(1,1);return 0 ;
}
//19:00-19:20/*
10 12 16
13 4 2 19
15 8 5 7 3
14 6 1 17
9 11 18*/
