dfs，排序
剪枝：这个题和前面有一道寒假作业的差不多，对每一行进行判断一下是否符合条件
#include<iostream> #include<cstring> using namespace std ; int cnt ; int m[5][5] ; bool v[20] ; bool check(){ bool flag = 1 ; for(int i = 0 ; i < 4 ; i ++){ if(m[i][0]+m[i][1]+m[i][2]+m[i][3] != 34) flag = 0; if(m[0][i]+m[1][i]+m[2][i]+m[3][i] != 34) flag = 0 ; } if(m[0][0]+m[1][1]+m[2][2]+m[3][3] != 34) flag = 0 ; if(m[3][0]+m[2][1]+m[1][2] +m[0][3] != 34) flag = 0 ; return flag ; } void dfs(int u){ if(u==16){ if(check()) cnt ++ ; return ; } //每一次填满新的一行，都检查一下这一行有没有满足条件，如果不满足就返回 if(u%4 == 0)if(m[u/4-1][0]+m[u/4-1][1]+m[u/4-1][2]+m[u/4-1][3] != 34) return ; for(int i = 2 ; i <= 16 ; i ++){ if(!v[i]){ m[u/4][u%4] = i; v[i] = 1 ; dfs(u+1) ; v[i] = 0; } } } int main(){ m[0][0] = 1 ; dfs(1); cout << cnt << endl ; return 0; }
