ソースコード
#include<stdio.h>
#include<stdlib.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,flg[21][21],bk,xo,yo,c=0; //cnt=道の総数,flg=マップ,xo=
void func(int,int,int); //目的の障害物の場所までの全探索
void func2(int,int,int); //目的の障害物の場所についてからの全探索
void func0(int,int,int);
int main(void){
int i,j,temp,B[10],
costh[8]={0,182,122,102,80,30,25,20},cost,flgt;
//マップ初期化
for(i=0;i<=20;i++){
for(j=0;j<=20;j++) flg[i][j]=0;
}
//入力
scInput();
cost=0; flgt=0;
for(i=0;i<scM;i++){
if(scB[0][i]+scB[1][i]<=scN/2){
bk=abs(scB[1][i])+abs(scB[0][i]);
for(j=1;j<=7;j++){
if(bk==j) cost+=costh[j];
}
}
}
if(cost>200) flgt=1;
if(flgt==0){
//障害物の座標の降順ソート
for(i=0;i<scM;i++) B[i]=abs(scB[0][i])+abs(scB[1][i]);
for(i=0;i<scM-1;i++){
for(j=i+1;j<scM;j++){
if(B[i]<B[j]){
temp=B[i]; B[i]=B[j]; B[j]=temp;
temp=scB[0][i]; scB[0][i]=scB[0][j]; scB[0][j]=temp;
temp=scB[1][i]; scB[1][i]=scB[1][j]; scB[1][j]=temp;
}
}
}
// for(i=0;i<scM;i++) printf("%d %d\n",scB[0][i],scB[1][i]);
if(scN==20) cnt=3273040;
else if(scN==18) cnt=549648;
else if(scN==16) cnt=94016;
else if(scN==14) cnt=16464;
c=0;
flg[10][10]=1; //出発地点を障害物にする
for(i=0;i<scM;i++){
if(scB[0][i]+scB[1][i]<=scN/2){
bk=abs(scB[1][i])+abs(scB[0][i]); //障害物から出発地点までの最短距離
xo=scB[0][i]; yo=scB[1][i]; //目的の障害物の座標を退避
flg[scB[1][i]+10][scB[0][i]+10]=2; //目的の障害物の場所を2に設定
func(10,10,0);
flg[scB[1][i]+10][scB[0][i]+10]=1; //目的の障害物を障害物に設定
}
}
}
else if(flgt==1){
int f=0;
for(i=0;i<scM;i++){
if(scB[0][i]+scB[1][i]<=scN/2){
f=1;
if(abs(scB[1][i])+abs(scB[0][i])==1) c++;
flg[scB[1][i]+10][scB[0][i]+10]=1;
}
}
if(f==0){ //分かっている数の場合
if(scN==20) cnt=3273040;
if(scN==18) cnt=549648;
if(scN==16) cnt=94016;
if(scN==14) cnt=16464;
}
else if(c>=3) cnt=0; //出発地点の隣が3つ以上障害物なら戻ってこれない
else {
cnt=0; //道の数初期化
flg[10][10]=1;
func0(10,10,0);
}
}
//出力
scOutput(cnt);
return 0;
}
void func(int x,int y,int c){
int i,j;
if(c<scN){
int xx=x,yy=y+1,bk2;//xx=次のx座標,yy=次のy座標,bk=戻るのに必要な距離
bk2=abs(xx-10-xo)+abs(yy-10-yo);
if(flg[yy][xx]!=1&&bk2+bk<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
if(flg[yy][xx]==2) func2(xx,yy,c+1); //目的の障害物の場所に着いたら別に関数呼び出し
else {
flg[yy][xx]=1;
func(xx,yy,c+1);
flg[yy][xx]=0;
}
}
xx=x+1,yy=y,bk2;
bk2=abs(xx-10-xo)+abs(yy-10-yo);
if(flg[yy][xx]!=1&&bk2+bk<=scN-(c+1)){
if(flg[yy][xx]==2) func2(xx,yy,c+1);
else {
flg[yy][xx]=1;
func(xx,yy,c+1);
flg[yy][xx]=0;
}
}
xx=x,yy=y-1,bk2;
bk2=abs(xx-10-xo)+abs(yy-10-yo);
if(flg[yy][xx]!=1&&bk2+bk<=scN-(c+1)){
if(flg[yy][xx]==2) func2(xx,yy,c+1);
else {
flg[yy][xx]=1;
func(xx,yy,c+1);
flg[yy][xx]=0;
}
}
xx=x-1,yy=y,bk2;
bk2=abs(xx-10-xo)+abs(yy-10-yo);
if(flg[yy][xx]!=1&&bk2+bk<=scN-(c+1)){
if(flg[yy][xx]==2) func2(xx,yy,c+1);
else {
flg[yy][xx]=1;
func(xx,yy,c+1);
flg[yy][xx]=0;
}
}
}
}
void func2(int x,int y,int c){
int i,j;
if(c<scN){ //進めるか
int xx=x,yy=y+1,bk2; //xx=次のx座標,yy=次のy座標
if(xx==10&&yy==10&&c+1==scN) cnt--; //出発地点に戻ってきたか
else {
bk2=abs(xx-10)+abs(yy-10); //bk=戻るのに必要な距離
if(flg[yy][xx]==0&&bk2<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
flg[yy][xx]=1; //その地点を障害物に設定にする
func2(xx,yy,c+1);
flg[yy][xx]=0; //その設定を解除
}
}
xx=x+1; yy=y;
if(xx==10&&yy==10&&c+1==scN) cnt--;
else {
bk2=abs(xx-10)+abs(yy-10);
if(flg[yy][xx]==0&&bk2<=scN-(c+1)){
flg[yy][xx]=1;
func2(xx,yy,c+1);
flg[yy][xx]=0;
}
}
xx=x; yy=y+-1;
if(xx==10&&yy==10&&c+1==scN) cnt--;
else {
bk2=abs(xx-10)+abs(yy-10);
if(flg[yy][xx]==0&&bk2<=scN-(c+1)){
flg[yy][xx]=1;
func2(xx,yy,c+1);
flg[yy][xx]=0;
}
}
xx=x+-1; yy=y;
if(xx==10&&yy==10&&c+1==scN) cnt--;
else {
bk2=abs(xx-10)+abs(yy-10);
if(flg[yy][xx]==0&&bk2<=scN-(c+1)){
flg[yy][xx]=1;
func2(xx,yy,c+1);
flg[yy][xx]=0;
}
}
}
}
void func0(int x,int y,int c){
if(c<scN){ //進めるか
int xx=x,yy=y+1,bk; //xx=次のx座標,yy=次のy座標
if(xx==10&&yy==10&&c+1==scN) cnt++; //出発地点に戻ってきたか
else {
bk=abs(xx-10)+abs(yy-10); //bk=戻るのに必要な距離
if(flg[yy][xx]==0&&bk<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
flg[yy][xx]=1; //その地点を障害物に設定にする
func0(xx,yy,c+1);
flg[yy][xx]=0; //その設定を解除
}
}
xx=x+1; yy=y; //xx=次のx座標,yy=次のy座標,
if(xx==10&&yy==10&&c+1==scN) cnt++; //出発地点に戻ってきたか
else {
bk=abs(xx-10)+abs(yy-10); //bk=戻るのに必要な距離
if(flg[yy][xx]==0&&bk<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
flg[yy][xx]=1; //その地点を障害物に設定にする
func0(xx,yy,c+1);
flg[yy][xx]=0; //その設定を解除
}
}
xx=x; yy=y+-1; //xx=次のx座標,yy=次のy座標,
if(xx==10&&yy==10&&c+1==scN) cnt++; //出発地点に戻ってきたか
else {
bk=abs(xx-10)+abs(yy-10); //bk=戻るのに必要な距離
if(flg[yy][xx]==0&&bk<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
flg[yy][xx]=1; //その地点を障害物に設定にする
func0(xx,yy,c+1);
flg[yy][xx]=0; //その設定を解除
}
}
xx=x+-1; yy=y; //xx=次のx座標,yy=次のy座標,
if(xx==10&&yy==10&&c+1==scN) cnt++; //出発地点に戻ってきたか
else {
bk=abs(xx-10)+abs(yy-10); //bk=戻るのに必要な距離
if(flg[yy][xx]==0&&bk<=scN-(c+1)){ //障害物でないか,出発地点へ戻ってこれるか
flg[yy][xx]=1; //その地点を障害物に設定にする
func0(xx,yy,c+1);
flg[yy][xx]=0; //その設定を解除
}
}
}
}