ソースコード
//sc1.hの内容を一番上にコピペする
#include<stdio.h>
#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));
}
//ここまでsc1.hの内容
//sc1.hをincludeするとCompile Errorになります
#include "algorithm"
const int SIZE = 100;
using namespace std;
int main(){
scInput();
int griding[200][200] = {};
int badding[200][200] = {};
int dp[200][200] = {};
int xe[4] = {0,0,1,-1};
int ye[4] = {1,-1,0,0};
int n = scN;
int back_trace[100] = {};
int now_itr = 0;
for(int i = 0;i < scM;++i){
if(abs(scB[0][i]) + abs(scB[1][i]) <= n){
griding[scB[0][i]+SIZE][scB[1][i]+SIZE] = 1;
}
}
for(int i = 0;i < 200;++i){
for(int q = 0;q < 200;++q){
badding[i][q] = abs(SIZE - i) + abs(SIZE - q); //Do not change this,because dp part will be broken if something changed.
}
}
for(int i = 0;i < 100;++i){
back_trace[i] = -1;
}
griding[SIZE][SIZE] = 1;
int now_x = SIZE;
int now_y = SIZE;
int ans = 0;
while(true){
int ok = 0;
for(int q = back_trace[now_itr]+1;q < 4;++q){
int go_x = now_x + xe[q];
int go_y = now_y + ye[q];
if(badding[go_x][go_y] <= n - now_itr - 1&&griding[go_x][go_y] == 0){
griding[go_x][go_y] = 1;
back_trace[now_itr] = q;
now_x = go_x;
now_y = go_y;
now_itr++;
ok = 1;
break;
}
}
if(badding[now_x][now_y] == n-now_itr){
//dp able!
ok = 0;
griding[SIZE][SIZE] = 0;
dp[1][1] = 1;
if(now_x < SIZE&&now_y < SIZE){
for(int i = now_x;i <= SIZE;++i){
for(int q = now_y;q <= SIZE;++q){
if(i != now_x||q != now_y){
if(griding[i][q] == 1){
dp[i-now_x+1][q-now_y+1] = 0;
}else{
dp[i - now_x + 1][q - now_y + 1] = dp[i-now_x][q - now_y + 1] + dp[i - now_x + 1][q - now_y];
}
}
}
}
ans += dp[SIZE - now_x + 1][SIZE - now_y + 1];
}else if(now_x >= SIZE&&now_y < SIZE){
for(int i = now_x;i >= SIZE;--i){
for(int q = now_y;q <= SIZE;++q){
if(i != now_x||q != now_y){
if(griding[i][q] == 1){
dp[now_x - i + 1][q-now_y+1] = 0;
}else{
dp[now_x - i + 1][q - now_y + 1] = dp[now_x - i][q - now_y + 1] + dp[now_x - i + 1][q - now_y];
}
}
}
}
ans += dp[now_x - SIZE + 1][SIZE - now_y + 1];
}else if(now_x < SIZE&&now_y >= SIZE){
for(int i = now_x;i <= SIZE;++i){
for(int q = now_y;q >= SIZE;--q){
if(i != now_x||q != now_y){
if(griding[i][q] == 1){
dp[i-now_x+1][now_y - q + 1] = 0;
}else{
dp[i - now_x + 1][now_y - q + 1] = dp[i-now_x][now_y - q + 1] + dp[i - now_x + 1][now_y - q];
}
}
}
}
ans += dp[SIZE - now_x + 1][now_y - SIZE + 1];
}else if(now_x >= SIZE&&now_y >= SIZE){
for(int i = now_x;i >= SIZE;--i){
for(int q = now_y;q >= SIZE;--q){
if(i != now_x||q != now_y){
if(griding[i][q] == 1){
dp[now_x - i+1][now_y - q + 1] = 0;
}else{
dp[now_x - i + 1][now_y - q + 1] = dp[now_x - i][now_y - q + 1] + dp[now_x - i + 1][now_y - q];
}
}
}
}
ans += dp[now_x - SIZE + 1][now_y - SIZE + 1];
}
griding[SIZE][SIZE] = 1;
}
if(ok == 0||(griding[SIZE-1][SIZE] == 1&&griding[SIZE+1][SIZE] == 1&&griding[SIZE][SIZE-1] == 1&&griding[SIZE][SIZE+1] == 1)){
back_trace[now_itr] = -1;
if(now_itr == 0){
scOutput(ans);
return 0;
}
now_itr--;
griding[now_x][now_y] = 0;
now_x -= xe[back_trace[now_itr]];
now_y -= ye[back_trace[now_itr]];
}
}
return 0;
}