結果

提出番号	1311
提出者	nii_nii
言語	C++
提出日時	2018-06-21 08:53:53
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	617000

---

テストケース

ソースコード

#include <stdio.h>
#include <vector>
#include<time.h>
//#include "sc1.h"
using namespace std;
//
//scN:SALの長さN=14,16,18,20
//scM:障害物の数M=1,2,3,4,5,6,7,8,9,10
//scB[2][10]:障害物の位置を表す座標を格納する配列
//scB[0][n]はn+1番目の障害物のx座標
//scB[1][n]はn+1番目の障害物のy座標
//

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));
}
int myabs(int n){//abs自作
    if(n>=0){
        return n;
    }else{
        return -n;
    }
}
//
int cul(int x,int y){//計算用
    return (x-(-10))+21*(y-(-10));
}
//
bool obst[441];//障害物ありますか
void read_obstacles(){
    obst[cul(0,0)]=1;//原点だめ
    for(int i=0;i<scM;i++){
        int x=scB[0][i],y=scB[1][i];
        if(myabs(x)+myabs(y)>scN/2){//絶対に通らない点は排除
            continue;
        }else{//通る可能性があったら
            obst[cul(x,y)]=1;
        }
    }
}
//
vector<vector<int> > road_to_vertex[441][4];//各頂点について行き方を格納//(-10,-10)が0番目です
int d[4]={-21,-1,1,21};
bool used[441];
void serch_road_to_vertex(int now,int cnt,vector<int> how_to_go){//DFS
    if(cnt==scN/2){
        int t=how_to_go[scN/2-1]-how_to_go[scN/2-2];//計算
        if(t==-21){//折り返し一歩手前でわけわけして格納
            road_to_vertex[now][0].push_back(how_to_go);
        }else if(t==-1){
            road_to_vertex[now][1].push_back(how_to_go);
        }else if(t==1){
            road_to_vertex[now][2].push_back(how_to_go);
        }else{
            road_to_vertex[now][3].push_back(how_to_go);            
        }
    }else{
        for(int i=0;i<4;i++){
            int nex=now+d[i];
            if(used[nex]==1){//既に通ってたらだめ
                continue;
            }else{//既に通ってないね
                if(obst[nex]==1){//障害物あったらだめ
                    continue;
                }else{
                    how_to_go.push_back(nex);
                    used[nex]=1;
                    serch_road_to_vertex(nex,cnt+1,how_to_go);//大丈夫なのでDFS
                    how_to_go.pop_back();
                    used[nex]=0;
                }
            }
        }
    }
}
//
int count_each_vertex_SAL(){
    int ans=0;
    for(int i=0;i<441;i++){
        int cnt=0;
        if(!road_to_vertex[i][0].empty()){
            cnt++;
        }
        if(!road_to_vertex[i][1].empty()){
            cnt++;
        }
        if(!road_to_vertex[i][2].empty()){
            cnt++;
        }
        if(!road_to_vertex[i][3].empty()){
            cnt++;
        }
        if(cnt<=1){//SALできません
            continue;
        }else{
            int bfrl=0,bfrm=0;//前回重なったところの記録(高速化)           
            for(int j=0;j<4;j++){//折り返し一歩手前が重ならないように全探索
                for(int k=j+1;k<4;k++){//同様
                    for(int l=0;l<(int)road_to_vertex[i][j].size();l++){//全探索
                        for(int m=0;m<(int)road_to_vertex[i][k].size();m++){//全探索
                            bool ok=1;
                            if(road_to_vertex[i][j][l][bfrl]==road_to_vertex[i][k][m][bfrm]){//前記録したとこ
                                continue;//だめ
                            }
                            for(int n=0;n<scN/2-1;n++){//交差判定
                                for(int o=n%2;o<scN/2-1;o+=2){//交差判定
                                    if(road_to_vertex[i][j][l][n]==road_to_vertex[i][k][m][o]){//交差判定
                                        ok=0;
                                        bfrl=n;bfrm=o;
                                        break;//だめ
                                    }
                                }
                                if(!ok){//だめ
                                    break;
                                }
                            }
                            if(ok){//いいよ
                                ans++;
                            }
                        }
                    }
                }
            }
        }
    }
    return ans;
}
//
int main(){
    scInput();//入力
    read_obstacles();//障害物の座標をbool値で管理
    vector<int> s;//次の行の関数に代入するためのモブ(特に意味はない)
    serch_road_to_vertex(220,0,s);//各頂点への行き方をDFS
    int ans=count_each_vertex_SAL()*2;//SALの数を数えよう逆順もあるよ
    scOutput(ans);//出力
    return 0;
}