ソースコード
#include <stdio.h>
#include <vector>
#include<time.h>
//#include "sc1.h"
using namespace std;
//
//scN:SALの長さN=14,16,18,20
//scM:障害物の数M=1,2,3,4,5,6,7,8,9,10
//scB[2][10]:障害物の位置を表す座標を格納する配列
//scB[0][n]はn+1番目の障害物のx座標
//scB[1][n]はn+1番目の障害物のy座標
//
int scN,scM;
int scB[2][10];
clock_t scStartTime,scEndTime;
void scInput(){
int i;
scanf("%d%d",&scN,&scM);
for(i=0;i<scM;++i){scanf("%d%d",&scB[0][i],&scB[1][i]);}
scStartTime=clock();
}
void scOutput(int s){
scEndTime=clock();
printf("Ans= %d, time=%d\n",s,(int)(scEndTime-scStartTime));
}
int myabs(int n){//abs自作
if(n>=0){
return n;
}else{
return -n;
}
}
//
int cul(int x,int y){//計算用
return (x-(-10))+21*(y-(-10));
}
//
bool obst[441]={};//障害物ありますか
void read_obstacles(){
obst[cul(0,0)]=1;//原点だめ
for(int i=0;i<scM;i++){
int x=scB[0][i],y=scB[1][i];
if(myabs(x)+myabs(y)>scN/2){//絶対に通らない点は排除
continue;
}else{//通る可能性があったら
obst[cul(x,y)]=1;
}
}
}
//
vector<vector<int> > road_to_vertex[441][4];//各頂点について行き方を格納//(-10,-10)が0番目です
int d[4]={-21,-1,1,21};
bool used[441]={};
void serch_road_to_vertex(int now,int cnt,vector<int> how_to_go){//DFS
if(cnt==scN/2){
int t=how_to_go[scN/2-1]-how_to_go[scN/2-2];//計算
if(t==-21){//折り返し一歩手前でわけわけして格納
road_to_vertex[now][0].push_back(how_to_go);
}else if(t==-1){
road_to_vertex[now][1].push_back(how_to_go);
}else if(t==1){
road_to_vertex[now][2].push_back(how_to_go);
}else{
road_to_vertex[now][3].push_back(how_to_go);
}
}else{
for(int i=0;i<4;i++){
int nex=now+d[i];
if(used[nex]){//既に通ってたらだめ
continue;
}else{//既に通ってないね
if(obst[nex]){//障害物あったらだめ
continue;
}else{
how_to_go.push_back(nex);
used[nex]=1;
serch_road_to_vertex(nex,cnt+1,how_to_go);//大丈夫なのでDFS
how_to_go.pop_back();
used[nex]=0;
}
}
}
}
}
//
int count_each_vertex_SAL(){
int ans=0;
for(int i=0;i<441;i++){
int cnt=0;
if(!road_to_vertex[i][0].empty()){
cnt++;
}
if(!road_to_vertex[i][1].empty()){
cnt++;
}
if(!road_to_vertex[i][2].empty()){
cnt++;
}
if(!road_to_vertex[i][3].empty()){
cnt++;
}
if(cnt<=1){//SALできません
continue;
}else{
int bfrl=0,bfrm=0;//前回重なったところの記録(高速化)
for(int j=0;j<4;j++){//折り返し一歩手前が重ならないように全探索
for(int k=j+1;k<4;k++){//同様
for(int l=0;l<(int)road_to_vertex[i][j].size();l++){//全探索
for(int m=0;m<(int)road_to_vertex[i][k].size();m++){//全探索
bool ok=1;
if(road_to_vertex[i][j][l][bfrl]==road_to_vertex[i][k][m][bfrm]){//前記録したとこ
continue;//だめ
}
for(int n=0;n<scN/2-1;n++){//交差判定
for(int o=n%2;o<scN/2-1;o+=2){//交差判定
if(road_to_vertex[i][j][l][n]==road_to_vertex[i][k][m][o]){//交差判定
ok=0;
bfrl=n;bfrm=o;
break;//だめ
}
}
if(!ok){//だめ
break;
}
}
if(ok){//いいよ
ans++;
}
}
}
}
}
}
}
return ans;
}
//
int main(){
scInput();//入力
read_obstacles();//障害物の座標をbool値で管理
vector<int> s;//次の行の関数に代入するためのモブ(特に意味はない)
serch_road_to_vertex(220,0,s);//各頂点への行き方をDFS
int ans=count_each_vertex_SAL()*2;//SALの数を数えよう逆順もあるよ
scOutput(ans);//出力
return 0;
}