ソースコード
#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));
}
int cnt,cnt2,cnt3,cnt4,sa,sa1,sa2,sa3,flg[40][40],i,j,a,b,g1,g2,g3,aut,l,has[4],p,q,sam,min;
int func(int,int,int);
int func2(int,int,int);
int func3(int,int,int);
int main(void)
{
int x,y;
//入力
scInput();
//マップ初期化
for(i=0;i<=scN;i++){
for(j=0;j<=scN;j++) flg[i][j]=0;
}
//分岐きめ
cnt3=0; g1=0; g2=0; g3=0; aut=0;
for(i=0;i<scM;i++){
x=scB[0][i]; y=scB[1][i];
flg[x+scN/2][y+scN/2]=1;
}
for(i=0;i<4;i++) has[i]=0;
//出入り口が埋まっているか
if(flg[scN/2+1][scN/2]==1) has[0]=1,cnt3++;
if(flg[scN/2][scN/2+1]==1) has[1]=1,cnt3++;
if(flg[scN/2-1][scN/2]==1) has[2]=1,cnt3++;
if(flg[scN/2][scN/2-1]==1) has[3]=1,cnt3++;
if(cnt3>1) aut=1;//ある一定範囲に障害物が一定数あったら分岐
for(i=scN/2-1;i<=scN/2+1;i++){
for(j=scN/2-1;j<=scN/2+1;j++) if(flg[i][j]==1) g1++;
}
if(g1>1) aut=1;
for(i=scN/2-2;i<=scN/2+2;i++){
for(j=scN/2-2;j<=scN/2+2;j++) if(flg[i][j]==1) g2++;
}
if(g2>2) aut=1;
for(i=0;i<=scN;i++){
for(j=0;j<=scN;j++) flg[i][j]=0;
}
flg[scN/2][scN/2]=2; //中心設置
cnt=0; //SWL
cnt2=0; //深さ
cnt3=0;
//障害物設置
if(aut==1&&cnt3<3){//足し算
cnt3=0;
//障害物設置
for(i=0;i<scM;i++){
x=scB[0][i]; y=scB[1][i];
flg[x+scN/2][y+scN/2]=1;
a=scN/2-(scN/2+x); b=scN/2-(scN/2+y);
if(a<0) a*=-1;
if(b<0) b*=-1;
if(a==1&&b==0||a==0&&b==1) cnt3++;
}
for(i=0;i<scM;i++){
x=scB[0][i]; y=scB[1][i];
flg[x+scN/2][y+scN/2]=1;
a=scN/2-(scN/2+x); b=scN/2-(scN/2+y);
if(a<0) a*=-1;
if(b<0) b*=-1;
if(a==1&&b==0||a==0&&b==1) cnt3++;
}
func(scN/2,scN/2,0);
}
else{//引き算
cnt=0; cnt2=0; cnt4=0; sam=0;
for(i=0;i<scM;i++) flg[scN/2+scB[0][i]][scN/2+scB[1][i]]=3; //障害物設置
flg[scN/2][scN/2]=2; //中心設置
for(l=0;l<scM;l++){
a=scB[0][l]; b=scB[1][l];
if(a<0) a*=-1;
if(b<0) b*=-1;
sa=a+b;
min=sa;
sa1=scN-a-b;
while(1){
cnt3=0;
if(sa1>=sa){
func2(scN/2,scN/2,0);
if(sa1>sa) sam+=cnt3*2;
else sam+=cnt3;
sa+=2; sa1-=2;
}
else break;
}
flg[scB[0][l]+scN/2][scB[1][l]+scN/2]=0;
}
if(scN==14) cnt=16464-sam;
else if(scN==16) cnt=94016-sam;
else if(scN==18) cnt=549648-sam;
else if(scN==20) cnt=3273040-sam;
}
//出力
scOutput(cnt);
return 0;
}
int func(int x1,int y1,int cnt1){ //x1とy1は現在地 cnt1は進んだ距離
// 最短で戻れる距離
a=scN/2-x1; b=scN/2-y1;
if(a<0) a*=-1;
if(b<0) b*=-1;
// 四方向見る
if(cnt1+1==scN&&flg[x1+1][y1]==2||cnt1+1==scN&&flg[x1][y1+1]==2||
cnt1+1==scN&&flg[x1-1][y1]==2||cnt1+1==scN&&flg[x1][y1-1]==2) cnt++; //最初の位置見る
else if(cnt1+a+b<=scN){
//下方向
if(flg[x1+1][y1]==0){
flg[x1+1][y1]=1; func(x1+1,y1,cnt1+1);
flg[x1+1][y1]=0;
}
//右方向
if(flg[x1][y1+1]==0){
flg[x1][y1+1]=1; func(x1,y1+1,cnt1+1);
flg[x1][y1+1]=0;
}
//上方向
if(flg[x1-1][y1]==0){
flg[x1-1][y1]=1; func(x1-1,y1,cnt1+1);
flg[x1-1][y1]=0;
}
//左方向
if(flg[x1][y1-1]==0){
flg[x1][y1-1]=1; func(x1,y1-1,cnt1+1);
flg[x1][y1-1]=0;
}
}
}
int func2(int x,int y,int cnt1){ //x,y現在地 cnt1進んだ距離
a=scN/2+scB[0][l]-x; b=scN/2+scB[1][l]-y;
if(a<0) a*=-1;
if(b<0) b*=-1;
sa2=a+b+cnt1;
if(sa2<=sa){
if(flg[x+1][y]==0){
flg[x+1][y]=1; func2(x+1,y,cnt1+1);
flg[x+1][y]=0;
}
else if(flg[x+1][y]==3&&cnt1+1==sa&&(scB[0][l]+scN/2==x+1&&scB[1][l]+scN/2==y)){
func3(x+1,y,0);
}
if(flg[x][y+1]==0){
flg[x][y+1]=1; func2(x,y+1,cnt1+1);
flg[x][y+1]=0;
}
else if(flg[x][y+1]==3&&cnt1+1==sa&&(scB[0][l]+scN/2==x&&scB[1][l]+scN/2==y+1)){
func3(x,y+1,0);
}
if(flg[x-1][y]==0){
flg[x-1][y]=1; func2(x-1,y,cnt1+1);
flg[x-1][y]=0;
}
else if(flg[x-1][y]==3&&cnt1+1==sa&&(scB[0][l]+scN/2==x-1&&scB[1][l]+scN/2==y)){
func3(x-1,y,0);
}
if(flg[x][y-1]==0){
flg[x][y-1]=1; func2(x,y-1,cnt1+1);
flg[x][y-1]=0;
}
else if(flg[x][y-1]==3&&cnt1+1==sa&&(scB[0][l]+scN/2==x&&scB[1][l]+scN/2==y-1)){
func3(x,y-1,0);
}
}
}
int func3(int x,int y,int cnt2){
a=scN/2-x; b=scN/2-y;
if(a<0) a*=-1;
if(b<0) b*=-1;
sa3=a+b+cnt2;
if(cnt2+1==sa1&&flg[x+1][y]==2||cnt2+1==sa1&&flg[x][y+1]==2||
cnt2+1==sa1&&flg[x-1][y]==2||cnt2+1==sa1&&flg[x][y-1]==2) cnt3++;
else if(sa3<=sa1){
//下方向
if(flg[x+1][y]==0){
flg[x+1][y]=1; func3(x+1,y,cnt2+1);
flg[x+1][y]=0;
}
//右方向
if(flg[x][y+1]==0){
flg[x][y+1]=1; func3(x,y+1,cnt2+1);
flg[x][y+1]=0;
}
//上方向
if(flg[x-1][y]==0){
flg[x-1][y]=1; func3(x-1,y,cnt2+1);
flg[x-1][y]=0;
}
//左方向
if(flg[x][y-1]==0){
flg[x][y-1]=1; func3(x,y-1,cnt2+1);
flg[x][y-1]=0;
}
}
}