結果

提出番号	1291
提出者	zohen0
言語	C++
提出日時	2018-06-20 21:59:00
問題名	(62)SuperCon2018(独自テスト)
結果	AC
点数	2619000

---

テストケース

ソースコード

#include <bitset>
#include <complex>
#include<stdio.h>
#include<time.h>
using namespace std;

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 dfs1(bitset<441> route, const int depth, int x, int y);
int dfs2(bitset<441> route, const int depth, int x, int y);
int dfs3(bitset<441> route, const int depth, int x, int y);
int dfs4(bitset<441> route, const int depth, int x, int y);

int dfs1(bitset<441> route, const int depth, int x, int y) {
  if(route[x * 21 + y] || (x == 10 && y == 10)) return 0;

  route[x * 21 + y] = true;

  int tx = abs(x - 10), ty = abs(y - 10);

  int s = (scN - depth) - (tx + ty);

  if(s < 0) return 0;
  if(depth == scN - 1) {
    if(y == 9) return 2;
    return 1;
  }
  if(s == 0) {
    int kx = x - 10, ky = y - 10, ktx = 10, kty = 10;
    int kh[32][32] = {};
    kh[x][y] = 1;
    int xk = 1, yk = 1;
    if(kx > 0) xk = -1;
    if(ky > 0) yk = -1;

    for(int i = 0; i <= tx; i++) {
      for(int j = 0; j <= ty; j++) {
        if(route[(x + i * xk) * 21 + y + j * yk] || !i && !j) continue;
        kh[x + i * xk][y + j * yk] = kh[x + i * xk - xk][y + j * yk] + kh[x + i * xk][y + j * yk - yk];
      }
    }

    return kh[10][10] + kh[10][9];
  }

  return dfs1(route, depth + 1, x + 1, y) + dfs2(route, depth + 1, x, y + 1) + dfs4(route, depth + 1, x, y - 1);
}

int dfs2(bitset<441> route, const int depth, int x, int y) {
  if(route[x * 21 + y] || (x == 10 && y == 10)) return 0;

  route[x * 21 + y] = true;

  int tx = abs(x - 10), ty = abs(y - 10);

  int s = (scN - depth) - (tx + ty);

  if(s < 0) return 0;
  if(depth == scN - 1) {
    if(y == 9) return 2;
    return 1;
  }
  if(s == 0) {
    int kx = x - 10, ky = y - 10, ktx = 10, kty = 10;
    int kh[32][32] = {};
    kh[x][y] = 1;
    int xk = 1, yk = 1;
    if(kx > 0) xk = -1;
    if(ky > 0) yk = -1;

    for(int i = 0; i <= tx; i++) {
      for(int j = 0; j <= ty; j++) {
        if(route[(x + i * xk) * 21 + y + j * yk] || !i && !j) continue;
        kh[x + i * xk][y + j * yk] = kh[x + i * xk - xk][y + j * yk] + kh[x + i * xk][y + j * yk - yk];
      }
    }

    return kh[10][10] + kh[10][9];
  }

  return dfs1(route, depth + 1, x + 1, y) + dfs2(route, depth + 1, x, y + 1) + dfs3(route, depth + 1, x - 1, y);
}

int dfs3(bitset<441> route, const int depth, int x, int y) {
  if(route[x * 21 + y] || (x == 10 && y == 10)) return 0;

  route[x * 21 + y] = true;

  int tx = abs(x - 10), ty = abs(y - 10);

  int s = (scN - depth) - (tx + ty);

  if(s < 0) return 0;
  if(depth == scN - 1) {
    if(y == 9) return 2;
    return 1;
  }
  if(s == 0) {
    int kx = x - 10, ky = y - 10, ktx = 10, kty = 10;
    int kh[32][32] = {};
    kh[x][y] = 1;
    int xk = 1, yk = 1;
    if(kx > 0) xk = -1;
    if(ky > 0) yk = -1;

    for(int i = 0; i <= tx; i++) {
      for(int j = 0; j <= ty; j++) {
        if(route[(x + i * xk) * 21 + y + j * yk] || !i && !j) continue;
        kh[x + i * xk][y + j * yk] = kh[x + i * xk - xk][y + j * yk] + kh[x + i * xk][y + j * yk - yk];
      }
    }

    return kh[10][10] + kh[10][9];
  }

  return dfs2(route, depth + 1, x, y + 1) + dfs3(route, depth + 1, x - 1, y) + dfs4(route, depth + 1, x, y - 1);
}

int dfs4(bitset<441> route, const int depth, int x, int y) {
  if(route[x * 21 + y] || (x == 10 && y == 10)) return 0;

  route[x * 21 + y] = true;

  int tx = abs(x - 10), ty = abs(y - 10);

  int s = (scN - depth) - (tx + ty);

  if(s < 0) return 0;
  if(depth == scN - 1) {
    if(y == 9) return 2;
    return 1;
  }
  if(s == 0) {
    int kx = x - 10, ky = y - 10, ktx = 10, kty = 10;
    int kh[32][32] = {};
    kh[x][y] = 1;
    int xk = 1, yk = 1;
    if(kx > 0) xk = -1;
    if(ky > 0) yk = -1;

    for(int i = 0; i <= tx; i++) {
      for(int j = 0; j <= ty; j++) {
        if(route[(x + i * xk) * 21 + y + j * yk] || !i && !j) continue;
        kh[x + i * xk][y + j * yk] = kh[x + i * xk - xk][y + j * yk] + kh[x + i * xk][y + j * yk - yk];
      }
    }

    return kh[10][10] + kh[10][9];
  }

  return dfs1(route, depth + 1, x + 1, y) + dfs3(route, depth + 1, x - 1, y) + dfs4(route, depth + 1, x, y - 1);
}

int main(void) {
  int ans;
  bitset<441> route;

  scInput();

  for(int i = 0; i < scM; i++) {
    if(scB[0][i] <= 10 && scB[0][i] >= -10 && scB[1][i] <= 10 && scB[1][i] >= -10) {
      route[(scB[0][i] + 10) * 21 + scB[1][i] + 10] = true;
    }
  }

  ans = dfs1(route, 1, 11, 10) + dfs2(route, 1, 10, 11) + dfs3(route, 1, 9, 10);

  scOutput(ans);
}