読者です 読者をやめる 読者になる 読者になる

AOJ 1103 Board Arrangements for Concentration Games

問題

AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ

解法

DFSで解きます。

コード

int board[4][4];
int dy[4], dx[4];

int dfs(int n){
  if(n >= 8) return 1;

  int res = 0;
  int y, x;
  rep(y, 4){
    rep(x, 4) if(!board[y][x]) break;
    if(x != 4) break;
  }

  int d;
  rep(d, 4){
    int ny = y+dy[d], nx = x+dx[d];
    if(ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || board[ny][nx] != 0) continue;
    board[y][x] = board[ny][nx] = 1;
    res += dfs(n+1);
    board[y][x] = board[ny][nx] = 0;
  }

  return res;
}

int main(){
  int i;
  while(1){
    rep(i, 4) if(scanf("%d%d", &dx[i], &dy[i])  && dx[0] >= 4) return 0;
    memset(board, 0, sizeof(board));

    printf("%d\n", dfs(0));
  }
  return 0;
}

iとかdをグローバル変数として宣言していた。スタック利用しないから再帰できないよね 条件もちゃんと読んでなかった