ソースコード
#include <iostream>
#include<stdio.h>
#include <algorithm>
#include <vector>
#include<time.h>
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));
}
using namespace std;
typedef long long ll;
struct f {
ll a, b, c;
};
int n, m, ans, k, i, j, z, l = -1;
int j0, j1, j2, j3, j4, j5, j6, j7, j8, j9, j10, j11, j12, j13, j14, j15;
vector<f>o[221][16];
bool v[21][21];
int h[21][21]={{0,0,0,0,0,0,0,0,0,0,199,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,188,152,200,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,186,150,127,153,201,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,184,148,118,90,128,154,202,0,0,0,0,0,0,0},{0,0,0,0,0,220,182,146,116,88,71,91,129,155,203,0,0,0,0,0,0},{0,0,0,0,0,180,144,114,86,64,44,72,92,130,156,204,0,0,0,0,0},{0,0,0,0,181,145,112,84,62,42,31,45,73,93,131,157,205,0,0,0,0},{0,0,0,183,147,113,85,60,40,26,14,32,46,74,94,132,158,206,0,0,0},{0,0,185,149,115,87,61,41,24,12,7,15,33,47,75,95,133,159,207,0,0},{0,187,151,117,89,63,43,25,13,4,0,8,16,34,48,76,96,134,160,208,0},{189,161,119,97,65,49,27,17,5,1,-1,3,10,23,38,59,82,111,142,179,218},{0,190,162,120,98,66,50,28,18,6,2,9,21,36,57,80,109,140,177,216,0},{0,0,191,163,121,99,67,51,29,19,11,20,35,55,78,107,138,175,214,0,0},{0,0,0,192,164,122,100,68,52,30,22,37,54,77,105,136,173,212,0,0,0},{0,0,0,0,193,165,123,101,69,53,39,56,79,104,135,171,210,0,0,0,0},{0,0,0,0,0,194,166,124,102,70,58,81,106,137,170,209,0,0,0,0,0},{0,0,0,0,0,0,195,167,125,103,83,108,139,172,211,0,0,0,0,0,0},{0,0,0,0,0,0,0,196,168,126,110,141,174,213,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,197,169,143,176,215,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,198,178,217,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,219,0,0,0,0,0,0,0,0,0,0}};
f p;
void dfs(int s, int x, int y) {
v[y][x] = true;
int u = h[y][x] / 63, d = h[y][x] % 63;
if (s) {
if (u == 0)p.a += ll(1) << d;
else if (u == 1)p.b += ll(1) << d;
else p.c += ll(1) << d;
}
if (s == n / 2 - 1) {
if (!v[y][x - 1])o[h[y][x - 1]][z].push_back(p);
if (!v[y][x + 1])o[h[y][x + 1]][z+1].push_back(p);
if (!v[y - 1][x])o[h[y - 1][x]][z+2].push_back(p);
if (!v[y + 1][x])o[h[y + 1][x]][z+3].push_back(p);
}
else {
if (!v[y][x - 1])dfs(s + 1, x - 1, y);
if (!v[y][x + 1])dfs(s + 1, x + 1, y);
if (!v[y + 1][x])dfs(s + 1, x, y + 1);
if (!v[y - 1][x])dfs(s + 1, x, y - 1);
}
v[y][x] = false;
if (s) {
if (u == 0)p.a -= ll(1) << d;
else if (u == 1)p.b -= ll(1) << d;
else p.c -= ll(1) << d;
}
}
int main(void) {
scInput();
n=scN;
m=scM;
for (i = 0; i<m; i++) {
int x, y;
x=scB[0][i];
y=scB[1][i];
x += 10;
y += 10;
if (0 <= x && x<21 && 0 <= y && y<21)v[y][x] = true;
}
v[10][10] = true;
z = 0;
if(!v[10][9])dfs(1, 9, 10);
z = 4;
if (!v[10][11])dfs(1, 11, 10);
z = 8;
if (!v[9][10])dfs(1, 10, 9);
z = 12;
if (!v[11][10])dfs(1, 10, 11);
for (k = 220; k+1; k--) {
vector<f> q0(o[k][0]); j0 = o[k][0].size();
vector<f> q1(o[k][1]); j1 = o[k][1].size();
vector<f> q2(o[k][2]); j2 = o[k][2].size();
vector<f> q3(o[k][3]); j3 = o[k][3].size();
vector<f> q4(o[k][4]); j4 = o[k][4].size();
vector<f> q5(o[k][5]); j5 = o[k][5].size();
vector<f> q6(o[k][6]); j6 = o[k][6].size();
vector<f> q7(o[k][7]); j7 = o[k][7].size();
vector<f> q8(o[k][8]); j8 = o[k][8].size();
vector<f> q9(o[k][9]); j9 = o[k][9].size();
vector<f> q10(o[k][10]); j10 = o[k][10].size();
vector<f> q11(o[k][11]); j11 = o[k][11].size();
vector<f> q12(o[k][12]); j12 = o[k][12].size();
vector<f> q13(o[k][13]); j13 = o[k][13].size();
vector<f> q14(o[k][14]); j14 = o[k][14].size();
vector<f> q15(o[k][15]); j15 = o[k][15].size();
for (i = j0 - 1; i + 1; i--) {
for (j = j5 - 1; j + 1; j--) {
if (!(q0[i].a&q5[j].a) && !(q0[i].b&q5[j].b) && !(q0[i].c&q5[j].c))ans++;
}
for (j = j6 - 1; j + 1; j--) {
if (!(q0[i].a&q6[j].a) && !(q0[i].b&q6[j].b) && !(q0[i].c&q6[j].c))ans++;
}
for (j = j7 - 1; j + 1; j--) {
if (!(q0[i].a&q7[j].a) && !(q0[i].b&q7[j].b) && !(q0[i].c&q7[j].c))ans++;
}
for (j = j9 - 1; j + 1; j--) {
if (!(q0[i].a&q9[j].a) && !(q0[i].b&q9[j].b) && !(q0[i].c&q9[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q0[i].a&q10[j].a) && !(q0[i].b&q10[j].b) && !(q0[i].c&q10[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q0[i].a&q11[j].a) && !(q0[i].b&q11[j].b) && !(q0[i].c&q11[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q0[i].a&q13[j].a) && !(q0[i].b&q13[j].b) && !(q0[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q0[i].a&q14[j].a) && !(q0[i].b&q14[j].b) && !(q0[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q0[i].a&q15[j].a) && !(q0[i].b&q15[j].b) && !(q0[i].c&q15[j].c))ans++;
}
}
for (i = j1 - 1; i + 1; i--) {
for (j = j4 - 1; j + 1; j--) {
if (!(q1[i].a&q4[j].a) && !(q1[i].b&q4[j].b) && !(q1[i].c&q4[j].c))ans++;
}
for (j = j6 - 1; j + 1; j--) {
if (!(q1[i].a&q6[j].a) && !(q1[i].b&q6[j].b) && !(q1[i].c&q6[j].c))ans++;
}
for (j = j7 - 1; j + 1; j--) {
if (!(q1[i].a&q7[j].a) && !(q1[i].b&q7[j].b) && !(q1[i].c&q7[j].c))ans++;
}
for (j = j8 - 1; j + 1; j--) {
if (!(q1[i].a&q8[j].a) && !(q1[i].b&q8[j].b) && !(q1[i].c&q8[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q1[i].a&q10[j].a) && !(q1[i].b&q10[j].b) && !(q1[i].c&q10[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q1[i].a&q11[j].a) && !(q1[i].b&q11[j].b) && !(q1[i].c&q11[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q1[i].a&q12[j].a) && !(q1[i].b&q12[j].b) && !(q1[i].c&q12[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q1[i].a&q14[j].a) && !(q1[i].b&q14[j].b) && !(q1[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q1[i].a&q15[j].a) && !(q1[i].b&q15[j].b) && !(q1[i].c&q15[j].c))ans++;
}
}
for (i = j2 - 1; i + 1; i--) {
for (j = j4 - 1; j + 1; j--) {
if (!(q2[i].a&q4[j].a) && !(q2[i].b&q4[j].b) && !(q2[i].c&q4[j].c))ans++;
}
for (j = j5 - 1; j + 1; j--) {
if (!(q2[i].a&q5[j].a) && !(q2[i].b&q5[j].b) && !(q2[i].c&q5[j].c))ans++;
}
for (j = j7 - 1; j + 1; j--) {
if (!(q2[i].a&q7[j].a) && !(q2[i].b&q7[j].b) && !(q2[i].c&q7[j].c))ans++;
}
for (j = j8 - 1; j + 1; j--) {
if (!(q2[i].a&q8[j].a) && !(q2[i].b&q8[j].b) && !(q2[i].c&q8[j].c))ans++;
}
for (j = j9 - 1; j + 1; j--) {
if (!(q2[i].a&q9[j].a) && !(q2[i].b&q9[j].b) && !(q2[i].c&q9[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q2[i].a&q11[j].a) && !(q2[i].b&q11[j].b) && !(q2[i].c&q11[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q2[i].a&q12[j].a) && !(q2[i].b&q12[j].b) && !(q2[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q2[i].a&q13[j].a) && !(q2[i].b&q13[j].b) && !(q2[i].c&q13[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q2[i].a&q15[j].a) && !(q2[i].b&q15[j].b) && !(q2[i].c&q15[j].c))ans++;
}
}
for (i = j3 - 1; i + 1; i--) {
for (j = j4 - 1; j + 1; j--) {
if (!(q3[i].a&q4[j].a) && !(q3[i].b&q4[j].b) && !(q3[i].c&q4[j].c))ans++;
}
for (j = j5 - 1; j + 1; j--) {
if (!(q3[i].a&q5[j].a) && !(q3[i].b&q5[j].b) && !(q3[i].c&q5[j].c))ans++;
}
for (j = j6 - 1; j + 1; j--) {
if (!(q3[i].a&q6[j].a) && !(q3[i].b&q6[j].b) && !(q3[i].c&q6[j].c))ans++;
}
for (j = j8 - 1; j + 1; j--) {
if (!(q3[i].a&q8[j].a) && !(q3[i].b&q8[j].b) && !(q3[i].c&q8[j].c))ans++;
}
for (j = j9 - 1; j + 1; j--) {
if (!(q3[i].a&q9[j].a) && !(q3[i].b&q9[j].b) && !(q3[i].c&q9[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q3[i].a&q10[j].a) && !(q3[i].b&q10[j].b) && !(q3[i].c&q10[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q3[i].a&q12[j].a) && !(q3[i].b&q12[j].b) && !(q3[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q3[i].a&q13[j].a) && !(q3[i].b&q13[j].b) && !(q3[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q3[i].a&q14[j].a) && !(q3[i].b&q14[j].b) && !(q3[i].c&q14[j].c))ans++;
}
}
for (i = j4 - 1; i + 1; i--) {
for (j = j9 - 1; j + 1; j--) {
if (!(q4[i].a&q9[j].a) && !(q4[i].b&q9[j].b) && !(q4[i].c&q9[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q4[i].a&q10[j].a) && !(q4[i].b&q10[j].b) && !(q4[i].c&q10[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q4[i].a&q11[j].a) && !(q4[i].b&q11[j].b) && !(q4[i].c&q11[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q4[i].a&q13[j].a) && !(q4[i].b&q13[j].b) && !(q4[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q4[i].a&q14[j].a) && !(q4[i].b&q14[j].b) && !(q4[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q4[i].a&q15[j].a) && !(q4[i].b&q15[j].b) && !(q4[i].c&q15[j].c))ans++;
}
}
for (i = j5 - 1; i + 1; i--) {
for (j = j8 - 1; j + 1; j--) {
if (!(q5[i].a&q8[j].a) && !(q5[i].b&q8[j].b) && !(q5[i].c&q8[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q5[i].a&q10[j].a) && !(q5[i].b&q10[j].b) && !(q5[i].c&q10[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q5[i].a&q11[j].a) && !(q5[i].b&q11[j].b) && !(q5[i].c&q11[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q5[i].a&q12[j].a) && !(q5[i].b&q12[j].b) && !(q5[i].c&q12[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q5[i].a&q14[j].a) && !(q5[i].b&q14[j].b) && !(q5[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q5[i].a&q15[j].a) && !(q5[i].b&q15[j].b) && !(q5[i].c&q15[j].c))ans++;
}
}
for (i = j6 - 1; i + 1; i--) {
for (j = j8 - 1; j + 1; j--) {
if (!(q6[i].a&q8[j].a) && !(q6[i].b&q8[j].b) && !(q6[i].c&q8[j].c))ans++;
}
for (j = j9 - 1; j + 1; j--) {
if (!(q6[i].a&q9[j].a) && !(q6[i].b&q9[j].b) && !(q6[i].c&q9[j].c))ans++;
}
for (j = j11 - 1; j + 1; j--) {
if (!(q6[i].a&q11[j].a) && !(q6[i].b&q11[j].b) && !(q6[i].c&q11[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q6[i].a&q12[j].a) && !(q6[i].b&q12[j].b) && !(q6[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q6[i].a&q13[j].a) && !(q6[i].b&q13[j].b) && !(q6[i].c&q13[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q6[i].a&q15[j].a) && !(q6[i].b&q15[j].b) && !(q6[i].c&q15[j].c))ans++;
}
}
for (i = j7 - 1; i + 1; i--) {
for (j = j8 - 1; j + 1; j--) {
if (!(q7[i].a&q8[j].a) && !(q7[i].b&q8[j].b) && !(q7[i].c&q8[j].c))ans++;
}
for (j = j9 - 1; j + 1; j--) {
if (!(q7[i].a&q9[j].a) && !(q7[i].b&q9[j].b) && !(q7[i].c&q9[j].c))ans++;
}
for (j = j10 - 1; j + 1; j--) {
if (!(q7[i].a&q10[j].a) && !(q7[i].b&q10[j].b) && !(q7[i].c&q10[j].c))ans++;
}
for (j = j12 - 1; j + 1; j--) {
if (!(q7[i].a&q12[j].a) && !(q7[i].b&q12[j].b) && !(q7[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q7[i].a&q13[j].a) && !(q7[i].b&q13[j].b) && !(q7[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q7[i].a&q14[j].a) && !(q7[i].b&q14[j].b) && !(q7[i].c&q14[j].c))ans++;
}
}
for (i = j8 - 1; i + 1; i--) {
for (j = j13 - 1; j + 1; j--) {
if (!(q8[i].a&q13[j].a) && !(q8[i].b&q13[j].b) && !(q8[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q8[i].a&q14[j].a) && !(q8[i].b&q14[j].b) && !(q8[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q8[i].a&q15[j].a) && !(q8[i].b&q15[j].b) && !(q8[i].c&q15[j].c))ans++;
}
}
for (i = j9 - 1; i + 1; i--) {
for (j = j12 - 1; j + 1; j--) {
if (!(q9[i].a&q12[j].a) && !(q9[i].b&q12[j].b) && !(q9[i].c&q12[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q9[i].a&q14[j].a) && !(q9[i].b&q14[j].b) && !(q9[i].c&q14[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q9[i].a&q15[j].a) && !(q9[i].b&q15[j].b) && !(q9[i].c&q15[j].c))ans++;
}
}
for (i = j10 - 1; i + 1; i--) {
for (j = j12 - 1; j + 1; j--) {
if (!(q10[i].a&q12[j].a) && !(q10[i].b&q12[j].b) && !(q10[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q10[i].a&q13[j].a) && !(q10[i].b&q13[j].b) && !(q10[i].c&q13[j].c))ans++;
}
for (j = j15 - 1; j + 1; j--) {
if (!(q10[i].a&q15[j].a) && !(q10[i].b&q15[j].b) && !(q10[i].c&q15[j].c))ans++;
}
}
for (i = j11 - 1; i + 1; i--) {
for (j = j12 - 1; j + 1; j--) {
if (!(q11[i].a&q12[j].a) && !(q11[i].b&q12[j].b) && !(q11[i].c&q12[j].c))ans++;
}
for (j = j13 - 1; j + 1; j--) {
if (!(q11[i].a&q13[j].a) && !(q11[i].b&q13[j].b) && !(q11[i].c&q13[j].c))ans++;
}
for (j = j14 - 1; j + 1; j--) {
if (!(q11[i].a&q14[j].a) && !(q11[i].b&q14[j].b) && !(q11[i].c&q14[j].c))ans++;
}
}
}
scOutput(ans*2);
}