結果

提出番号	1303
提出者	WA_TLE
言語	C++
提出日時	2018-06-20 22:30:12
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	2637000

---

テストケース

ソースコード

#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));
}
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cmath>
#include<array>
using namespace std;
#define llint long long
const int ntyu=10;//真ん中
const int basiz=21;
struct state{
	array<int,basiz>ban;
	int gy,gx;
};
const int dx[4]={1,0,-1,0};
const int dy[4]={0,-1,0,1};
llint solve(state&in,int turn){
	//状態、残りターン
	if(turn!=scN&&in.gy==ntyu&&in.gx==ntyu){return 0;}
	if(abs(ntyu-in.gy)+abs(ntyu-in.gx)>turn){return 0;}
	if(turn==1){return 1;}//必ず1通りなので
	llint ans=0;
	for(int d=0;d<4;d++){
		int ny=in.gy+dy[d];
		int nx=in.gx+dx[d];
		if(ny<0||ny>basiz||nx<0||nx>basiz){continue;}
		if((in.ban[ny])&(1<<nx)){continue;}//そこにはすでに訪れている
		in.ban[ny]+=(1<<nx);
		in.gy+=dy[d];
		in.gx+=dx[d];
		ans+=solve(in,turn-1);
		in.ban[ny]-=(1<<nx);
		in.gy-=dy[d];
		in.gx-=dx[d];//戻している
	}
	return ans;
}
int main(void){
	scInput();
	state in;
	in.gy=ntyu;
	in.gx=ntyu;
	for(int i=0;i<basiz;i++){in.ban[i]=0;}
	for(int i=0;i<scM;i++){
		int sy=scB[0][i]+ntyu;
		int sx=scB[1][i]+ntyu;
		if(sy<0||sy>basiz||sx<0||sx>basiz){continue;}
		in.ban[sy]+=(1<<sx);
	}
	scOutput(solve(in,scN));
	
	return 0;
}