lanqiao OJ 664 方格填数

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 500;
int mp[10][10] ;
int cnt ;
int v[N] ;
int d[4][2] = {{0,-1},{-1,0},{-1,-1},{-1,1}} ;
bool check(int x, int y){//检查一下四个方向的数是否合法
  bool flag = 1 ;
  int a = mp[x][y] ;
  for(int i =0 ; i < 4 ; i ++){
    int tx = x + d[i][0] , ty = y + d[i][1] ;
    if(tx < 0 || tx >= 3 || ty < 0 || ty >= 4) continue ;
    int b = mp[tx][ty] ;
    if(b == a-1 || b == a+1) flag = 0 ;
  }
  return flag ;
}
 
void dfs(int u){
  if(u == 11){
    cnt ++ ;
    return ;
  }
  for(int i = 0 ; i < 10 ; i ++){//全排列
    if(!v[i]){
      mp[u/4][u%4] = i ;
      if(!check(u/4,u%4)) continue ;
      v[i] = 1 ;
      dfs(u+1) ;
      v[i] = 0 ;
    }
  }
}
 
int main(){
  mp[0][0] = N ;
  mp[2][3] = N ;
  for(int i = 0 ; i < 4 ; i ++) {
    mp[3][i] = N , mp[i][4] = N ;
  }
  
  dfs(1) ;
  cout << cnt << endl ;
  return 0 ; 
}