結果

提出番号	1271
提出者	HIBIKU
言語	C++
提出日時	2018-06-20 21:24:15
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	2796000

---

テストケース

ソースコード

#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 <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
int ans=0;
int vx[4] = { 1,0,-1,0 }, vy[4] = { 0,1,0,-1 };
void dfs(int n, bool f[100][100], int x, int y){
	if(n>=scN){
		if(x==50&&y==50){
			ans++;
		}
		return;
	}
	if (n > scN / 2 && n < scN) {
		if (abs(50 - x) + abs(50 - y) > scN - n) return;
	}
	
	for(int i=0;i<4;i++){
		int nx = x + vx[i], ny = y + vy[i];
		if(!f[nx][ny]&&!(nx==50&&ny==50&&n==scN-1)) continue;
		if (n == scN - 1 && (nx != 50 || ny != 50)) continue;
		f[nx][ny]=false;
		dfs(n+1,f,nx,ny);
		f[nx][ny]=true;
		f[50][50] = false;
	}
}	

int main(){
	scInput();
	bool f[100][100];
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			f[i][j] = true;
		}
	}
	for (int i = 0; i < scM; i++) {
		int sx=scB[0][i]+50;
		int sy=scB[1][i]+50;
		if(0<=sx&&sx<100&&0<=sy&&sy<100) f[sx][sy] = false;
	}
	f[50][50]=false;
	dfs(0,f,50,50);
	scOutput(ans);
	return 0;
}