AOJ 2163 Tatami

問題

Tatami

1:2の大きさの畳をH,Wの大きさの部屋に敷き詰める方法は何通りあるか。 畳の敷き詰め方のルールに乗っ取って敷き詰めて行きます。

解法

畳を敷き詰めるルールは日本人なら誰でも分かるので説明の必要はありませんね。DFSで全探索すれば解けます。 ちなみに7.07secでした制限ぎりぎり、

心臓に悪いコード

int H, W, t[20][20];
int dy[] = {0, 1}, dx[] = {1,0}; // 横　縦

int judge(int y, int x){
  map<int, int>m;
  for(int i = -1; i < 1; i++){
    for(int j = -1; j < 1; j++){
      int ny = y+i, nx = x+j;
      if(ny < 0 || nx < 0 || t[ny][nx] == -1 || m.count(t[ny][nx])) continue;
      m[t[ny][nx]] = 1;
    }
  }
  if(m.size() < 4) return 1;
  return 0;
}

int dfs(int n){
  int i, j, res = 0;
  for(i = 0; i < H; i++) for(j = 0; j < W; j++) if(t[i][j] == -1) goto b;
 b:

  if(i == H && j == W) return 1;

  int tmp[20][20];
  rep(i, H) rep(j, W) tmp[i][j] = t[i][j];

  t[i][j] = n;
  rep(d, 2){
    int x = j+dx[d], y = i+dy[d];
    if(x < 0 || x >= W || y < 0 || y >= H || t[y][x] != -1) continue;
    t[y][x] = n;
    if(judge(i, j)) res += dfs(n+1);
    t[y][x] = -1;
  }
  rep(i, H) rep(j, W) t[i][j] = tmp[i][j];

  return res;
}

int main(){
  while(scanf("%d%d", &H, &W) && H+W){
    memset(t, -1, sizeof(t));
    printf("%d\n", dfs(0));
  }
  return 0;
}

tmpに移動するループを20からH,Wにして4.39sになった

int H, W, t[20][20];
int dy[] = {0, 1}, dx[] = {1,0}; // 横　縦

int judge(int y, int x){
  map<int, int>m;
  for(int i = -1; i < 1; i++){
    for(int j = -1; j < 1; j++){
      int ny = y+i, nx = x+j;
      if(ny < 0 || nx < 0 || t[ny][nx] == -1 || m.count(t[ny][nx])) continue;
      m[t[ny][nx]] = 1;
    }
  }
  if(m.size() < 4) return 1;
  return 0;
}

int dfs(int n){
  int i, j, res = 0;
  for(i = 0; i < H; i++) for(j = 0; j < W; j++) if(t[i][j] == -1) goto b;
 b:

  if(i == H && j == W) return 1;

  t[i][j] = n;
  rep(d, 2){
    int x = j+dx[d], y = i+dy[d];
    if(x < 0 || x >= W || y < 0 || y >= H || t[y][x] != -1) continue;
    t[y][x] = n;
    if(judge(i, j)) res += dfs(n+1);
    t[y][x] = -1;
  }
  t[i][j] = -1;

  return res;
}

int main(){
  while(scanf("%d%d", &H, &W) && H+W){
    memset(t, -1, sizeof(t));
    printf("%d\n", dfs(0));
  }
  return 0;
}

そもそもtmpに移動させる必要はなかった2.31s

int H, W, t[20][20];
int dy[] = {0, 1}, dx[] = {1,0}; // 横　縦

int judge(int y, int x){
  map<int, int>m;
  for(int i = -1; i < 1; i++){
    for(int j = -1; j < 1; j++){
      int ny = y+i, nx = x+j;
      if(ny < 0 || nx < 0 || t[ny][nx] == -1 || m.count(t[ny][nx])) continue;
      m[t[ny][nx]] = 1;
    }
  }
  if(m.size() < 4) return 1;
  return 0;
}

int dfs(int n){
  int i, j, res = 0;
  for(i = 0; i < H; i++) for(j = 0; j < W; j++) if(t[i][j] == -1) goto b;
 b:

  if(i == H && j == W) return 1;

  t[i][j] = n;
  rep(d, 2){
    int x = j+dx[d], y = i+dy[d];
    if(x < 0 || x >= W || y < 0 || y >= H || t[y][x] != -1) continue;
    t[y][x] = n;
    if(judge(i, j)) res += dfs(n+1);
    t[y][x] = -1;
  }
  t[i][j] = -1;

  return res;
}

int main(){
  while(scanf("%d%d", &H, &W) && H+W){
    memset(t, -1, sizeof(t));
    if(H%2 && W%2) puts("0");
    else if(H == W) puts("2");
    else printf("%d\n", dfs(0));
  }
  return 0;
}
``
`


同じ数で偶数なら2、奇数同士だと0になる1.95s。実際の再帰で時間が掛かってる。