結果

提出番号	1264
提出者	pluton
言語	C++
提出日時	2018-06-20 21:08:47
問題名	(62)SuperCon2018(独自テスト)
結果	CE
点数	0

---

テストケース

ソースコード

//SuperCon 2018 予選問題1級
//
//チーム名: COREDUMP(こあだんぷ)
​
#include <algorithm>
#include <cstdio>

#define ORIGIN 20
//原点を(20, 20)とします

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));
}
​
​
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
​
bool map[ORIGIN * 2][ORIGIN * 2];
int ans = 0;
​
void dfs(int x = ORIGIN, int y = ORIGIN, int count = 0);
//長さがNで原点に戻るSALをDFS（深さ優先探索)で探索する関数の宣言です
​
int main(){
​
    scInput();
​
	for(int i = 0; i < scM; ++i){
		map[scB[0][i] + ORIGIN][scB[1][i] + ORIGIN] = true;
	}
	//予め障害物の座標を保存しておきます
	dfs();
​
    scOutput(ans);
​
    return 0;
}
​
void dfs(int x, int y, int count){
    int dis = std::abs(x - ORIGIN) + std::abs(y - ORIGIN);
	if(dis > scN - count){
		return;
	}
	//原点からの距離が残りの回数で戻れる距離より大きいときに探索を中止します
​
	if(dis == 0 && count > 0){
		if(scN == count){
			++ans;
		}
		return;
	}
	//原点に到達し、長さがNの場合のみ、答えに1を足します
	
    for(int i = 0; i < 4; i++){
        int rx = x + dx[i];
        int ry = y + dy[i];
​
        if(!map[rx][ry]){
            map[rx][ry] = true;
            dfs(rx, ry, count + 1);
            map[rx][ry] = false;                
        }
    }
}