結果

提出番号	1270
提出者	Nafmo
言語	C++
提出日時	2018-06-20 21:19:11
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	3073000

---

テストケース

ソースコード

#include<stdio.h>
#include<cmath>
#include<algorithm>
#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;
//ans：答え F：訪問済チェック v：方向要素保存 dx,dy：移動方向差分
int ans;
bool F[50][50];
int v[5],dx[4],dy[4];
// x座標 y座標 回数 方向
inline void DFS(int x,int y,int d,int dr){
	if(d == scN){
		//左右と上下に動いた回数が同じであるかと
		//N回進んだときにスタート地点に戻ることを確認する
		if(v[0] != v[2] || v[1] != v[3])return;
		if(x == 0 && y == 0)++ans;
		return;
	}
	//今いる地点から残りの移動回数で戻れなければ枝刈り。
	if(abs(x)+abs(y)>scN-d)return;
	//移動方向 右:0 上:1 左:2 下:3
	for(int i=0;i!=4;++i){
		//一個前の座標の位置に動くのを防ぐ
		if(dr == i)continue;
		//一度通ったマスでなければ再帰する。
		if(!F[x + dx[i] + 20][y + dy[i] + 20]){
			F[x + dx[i] + 20][y + dy[i] + 20] = true;
			++v[i];
			//進んだ方向と逆には進めないためそれを渡して再帰する
			int a=(i+2)%4;
			DFS(x + dx[i],y + dy[i],d + 1,a);
			--v[i]; F[x + dx[i] + 20][y + dy[i] + 20] = false;
		}
	}
}

int main(){
	scInput();
	//scInput() より前に実行してはいけないため（初期化も不可）
	v[0]=v[1]=v[2]=v[3]=0;
	dx[0]=1,dx[1]=0,dx[2]=-1,dx[3]=0;
	dy[0]=0,dy[1]=-1,dy[2]=0,dy[3]=1;
	for (int i=0;i!=scM;++i)F[scB[0][i]+20][scB[1][i]+20] = true;
	if(!F[20][20])DFS(0,0,0,-1);
	scOutput(ans);
	return 0;
}