lanqiao OJ 689 四阶幻方

#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;
}