记录编号	278912	评测结果	WWWWWWWWWW
题目名称	[USACO 1.5.4] 跳棋的挑战	最终得分	0
用户昵称	Ge0Bi1Lao0W	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-07-08 16:43:44	内存使用	0.31 MiB

#include <iostream>
#include <fstream>
#include <algorithm>
#define local
using namespace std;

int N;
int pos[14];
int safe[14][14]; //0安全 1不安全
int sum;
int back;
ofstream fout ("checker.out");
ifstream fin ("checker.in");
/*
void check(int i){
  //检查i行以后每行是否有安全位置
  int a;
  int sum;
  for(;i<=N;i++){
    for(a=1;a<=N;a++){
      if(safe[i][a]==1)
        sum;
    }
  }
}
*/

void calc(int i){
  int a,b,x;
  //根据i-1行计算全局安全位置
  if(back<i){
    //不回溯 只刷新下面一行
    //正斜率 k1= i(行) + pos[i](列)
    //负斜率 k2= i(行) - pos[i](列)
    //竖直 k3= pos[i](列)
    x=i-1;
    for(a=i;a<=N;a++){
      if( (x+pos[x]-a>=1) && (x+pos[x]-a<=N))
        safe[a][x+pos[x]-a]=1;
      if((a-(x-pos[x])>=1) && (a-(x-pos[x])<=N))
		  safe[a][a-(x-pos[x])]=1;
	  safe[a][pos[x]]=1;
      //cout<<safe[a][1]<<safe[a][2]<<safe[a][3]<<safe[a][4]<<safe[a][5]<<safe[a][6]<<safe[a][7]<<safe[a][8]<<safe[a][9]<<endl;
    }
    
  }
  else{
    //清空包括i行以下所有状态
    //重新填充
    for(a=i;a<=N;a++){
      for(b=1;b<=N;b++)
        safe[a][b]=0;
    }
    x=i-1;
    for(a=1;a<=i-1;a++){
      for(b=i;b<=N;b++){
        if( (a+pos[a]-b>=1) && (a+pos[a]-b<=N))
          safe[b][a+pos[a]-b]=1;
        if( (b-(a-pos[a])>=1) && (b-(a-pos[a])<=N))
		safe[b][b-(a-pos[a])]=1;
        safe[b][pos[a]]=1;
      }
      //cout<<safe[b][1]<<safe[b][2]<<safe[b][3]<<safe[b][4]<<safe[b][5]<<safe[b][6]<<safe[b][7]<<safe[b][8]<<safe[b][9]<<endl;
    }
  }
  back=i;
  /*
  for(a=1;a<=N;a++){
    for(b=1;b<=N;b++)
      cout<<safe[a][b]<<' ';
    cout<<endl;
  }
  cout<<endl;
  */
  return;
}

void DFS(int i,int j){
  int a;
  int p;
  //计算第i行j列的解
  if(i==N){
    //边界
    if(sum<3){
      pos[i]=j;
      #ifdef local
        for(a=1;a<N;a++)
          cout<<pos[a]<<' ';
        cout<<pos[a]<<endl;
      #else
        for(a=1;a<N;a++)
          fout<<pos[a]<<' ';
        fout<<pos[a]<<endl;
      #endif
    }
    sum++;
  }
  else if(i==1){
    //第一行
    pos[i]=j;
    calc(2); //计算第二行
    for(a=1;a<=N;a++){
      if(safe[i+1][a]==1)
        continue;
      else{
        DFS(i+1,a);
      }
    }
  }
  else{
    pos[i]=j;
    calc(i+1);
    for(a=1;a<=N;a++){
      if(safe[i+1][a]==1)
        continue;
      else
        DFS(i+1,a);
    }
  }
  return;
}

int main() {
  int i;
  

  
  #ifdef local
    cin>>N;
  #else
    fin>>N;
  #endif
  
  if(N==6){
    for(i=1;i<=N;i++)
      DFS(1,i);
  }
  else if(N%2==0){
    for(i=1;i<=N/2;i++)
      DFS(1,i);
    sum*=2;
  }
  else{
    for(i=1;i<=N/2;i++)
      DFS(1,i);
    sum*=2;
    DFS(1,N/2+1);
  }
    
  #ifdef local
    cout<<sum<<endl;
  #else
    fout<<sum<<endl;
  #endif
  
  return 0;
  
}