結果

提出番号	1281
提出者	kotamanegi
言語	C++
提出日時	2018-06-20 21:52:05
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	1190000

---

テストケース

ソースコード

//sc1.hの内容を一番上にコピペする
#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));
}
//ここまでsc1.hの内容
//sc1.hをincludeするとCompile Errorになります
#include "algorithm"

const int SIZE = 100;
using namespace std;
int main(){
	scInput();
	int griding[200][200] = {};
	int badding[200][200] = {};
	int dp[200][200] = {};
	int xe[4] = {0,0,1,-1};
	int ye[4] = {1,-1,0,0};
	int n = scN;
	int back_trace[100] = {};
	int now_itr = 0;
	for(int i = 0;i < scM;++i){
		if(abs(scB[0][i]) + abs(scB[1][i]) <= n){
			griding[scB[0][i]+SIZE][scB[1][i]+SIZE] = 1;
		}
	}
	for(int i = 0;i < 200;++i){
		for(int q = 0;q < 200;++q){
			badding[i][q] = abs(SIZE - i) + abs(SIZE - q);	//Do not change this,because dp part will be broken if something changed.
		}
	}
	for(int i = 0;i < 100;++i){
		back_trace[i] = -1;
	}
	griding[SIZE][SIZE] = 1;
	int now_x = SIZE;
	int now_y = SIZE;
	int ans = 0;
	while(true){
		int ok = 0;
			for(int q = back_trace[now_itr]+1;q < 4;++q){
				int go_x = now_x + xe[q];
				int go_y = now_y + ye[q];
				if(badding[go_x][go_y] <= n - now_itr - 1&&griding[go_x][go_y] == 0){
					griding[go_x][go_y] = 1;
					back_trace[now_itr] = q;
					now_x = go_x;
					now_y = go_y;
					now_itr++;
					ok = 1;
					break;
				}
			}
			if(badding[now_x][now_y] == n-now_itr){
				//dp able!
				ok = 0;
				griding[SIZE][SIZE] = 0;
				dp[1][1] = 1;
				if(now_x < SIZE&&now_y < SIZE){
					for(int i = now_x;i <= SIZE;++i){
						for(int q = now_y;q <= SIZE;++q){
							if(i != now_x||q != now_y){
								if(griding[i][q] == 1){
									dp[i-now_x+1][q-now_y+1] = 0;
								}else{
									dp[i - now_x + 1][q - now_y + 1] = dp[i-now_x][q - now_y + 1] + dp[i - now_x + 1][q - now_y];
								}
							}
						}
					}
					ans += dp[SIZE - now_x + 1][SIZE - now_y + 1];
				}else if(now_x >= SIZE&&now_y < SIZE){
					for(int i = now_x;i >= SIZE;--i){
						for(int q = now_y;q <= SIZE;++q){
							if(i != now_x||q != now_y){
								if(griding[i][q] == 1){
									dp[now_x - i + 1][q-now_y+1] = 0;
								}else{
									dp[now_x - i + 1][q - now_y + 1] = dp[now_x - i][q - now_y + 1] + dp[now_x - i + 1][q - now_y];
								}
							}
						}
					}
					ans += dp[now_x - SIZE + 1][SIZE - now_y + 1];
				}else if(now_x < SIZE&&now_y >= SIZE){
					for(int i = now_x;i <= SIZE;++i){
						for(int q = now_y;q >= SIZE;--q){
							if(i != now_x||q != now_y){
								if(griding[i][q] == 1){
									dp[i-now_x+1][now_y - q + 1] = 0;
								}else{
									dp[i - now_x + 1][now_y - q + 1] = dp[i-now_x][now_y - q + 1] + dp[i - now_x + 1][now_y - q];
								}
							}
						}
					}
					ans += dp[SIZE - now_x + 1][now_y - SIZE + 1];
				}else if(now_x >= SIZE&&now_y >= SIZE){
					for(int i = now_x;i >= SIZE;--i){
						for(int q = now_y;q >= SIZE;--q){
							if(i != now_x||q != now_y){
								if(griding[i][q] == 1){
									dp[now_x - i+1][now_y - q + 1] = 0;
								}else{
									dp[now_x - i + 1][now_y - q + 1] = dp[now_x - i][now_y - q + 1] + dp[now_x - i + 1][now_y - q];
								}
							}
						}
					}
					ans += dp[now_x - SIZE + 1][now_y - SIZE + 1];
				}
				griding[SIZE][SIZE] = 1;
			}
			if(ok == 0||(griding[SIZE-1][SIZE] == 1&&griding[SIZE+1][SIZE] == 1&&griding[SIZE][SIZE-1] == 1&&griding[SIZE][SIZE+1] == 1)){
				back_trace[now_itr] = -1;
				if(now_itr == 0){
					scOutput(ans);
					return 0;
				}
				now_itr--;
				griding[now_x][now_y] = 0;
				now_x -= xe[back_trace[now_itr]];
				now_y -= ye[back_trace[now_itr]];
			}
	}
	return 0;
}