結果

提出番号	1307
提出者	callsnote
言語	C++
提出日時	2018-06-20 22:55:00
問題名	(62)SuperCon2018(独自テスト)
結果	CE
点数	0

---

テストケース

ソースコード

#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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

#ifdef LOCAL
#include <iostream>
#define db std::cout << "L" << __LINE__ <<
#define de << "\n"
#define dv(x) << " " << #x << "->" << x
#else
#define db
#define de
#define dv(x)
#endif

//
// Implementation
//

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

#define MAX_N 20
#define BIT_N (MAX_N*2*MAX_N*2)

bool path[MAX_N*2][MAX_N*2];
bool trap[MAX_N*2][MAX_N*2];

struct Point {
  int x;
  int y;
};
bool operator <(Point a, Point b) {
  return (a.x < b.x) || ((!(b.x < a.x)) && (a.y < b.y));
}
bool operator ==(Point a, Point b) {
  return a.x == b.x && a.y == b.y;
}
bool operator !=(Point a, Point b) {
  return !(a == b);
}
struct Route {
  Point p[10];
};

vector<Route> routemap[MAX_N*2][MAX_N*2];

void collect_routes(int x, int y, int len, Route route) {
  if (abs((x-scN)*(x-scN))+abs((y-scN)*(y-scN)) > (scN-len)*(scN-len)) return;
  if (path[y][x]) return;
  if (trap[y][x]) return;
  if (len == scN/2) {
    routemap[y][x].push_back(route);
    return;
  }

  path[y][x] = true;
  route.p[len] = (Point){x, y};
  collect_routes(x+1, y, len+1, route);
  collect_routes(x-1, y, len+1, route);
  collect_routes(x, y+1, len+1, route);
  collect_routes(x, y-1, len+1, route);
  path[y][x] = false;
}

bool is_duplicate(bool visited[MAX_N*2][MAX_N*2], Route b) {
  for (int i=1; i<scN/2; i++) {
    if (visited[b.p[i].y][b.p[i].x]) return true;
  }
  return false;
}

void debug_route(Route route) {
  for (int i=1; i<scN/2; i++) {
    printf("%d:%d ", route.p[i].x-scN, route.p[i].y-scN);
  }
}

int combine_routes() {
  int acc = 0;
  for (int y=scN/2; y<=scN+scN/2; y++) {
    for (int x=scN/2; x<=scN+scN/2; x++) {
      vector<Route> routes = routemap[y][x];
      // printf("%d:%d routes.size()=%d\n", x-scN, y-scN, routes.size());
      rep(i, routes.size()) {
        bool visited[MAX_N*2][MAX_N*2] = {};
        for (int j=1; j<scN/2; j++) {
          visited[routes[i].p[j].y][routes[i].p[j].x] = true;
        }
        for (int j=i+1; j<routes.size(); j++) {
          if (is_duplicate(visited, routes[j])) continue;
          acc++;
        }
      }
    }
  }
  return acc*2;
}

int main() {
  scInput();

  rep(i, scM) {
    int x = scB[0][i];
    int y = scB[1][i];
    if (x+scN < 0 || y+scN < 0 || x+scN >= MAX_N*2 || y+scN >= MAX_N*2) continue;
    trap[x+scN][y+scN] = true;
  }
  collect_routes(scN, scN, 0, (Route){});
  int acc = combine_routes();
  scOutput(acc);
}