日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_13】A: Heuristic Search - 8 Queens Problem

問題

| アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • バックトラック法を用いて探索を行おう.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define N 8

using namespace std;

bool isLocated[N][N];
int row[N];     // 行方向の襲撃
int col[N];     // 列方向の襲撃
int dl[2*N-1];  // 左下への襲撃
int dr[2*N-1];  // 右下への襲撃

void print(){
  rep(i, N){
    rep(j, N){
      if(isLocated[i][j] && row[i] != j) return;
    }
  }

  rep(i, N){
    rep(j, N){
      cout << (row[i] == j?"Q":".");
    }
    cout << "\n";
  }
}

void solve(int i){

  // すべての行置き終わった
  if(i == N){
    print();
    return;
  }

  // すべての列試す
  rep(j, N){
    // すでに襲撃されている場合
    if(col[j] == 1 || dl[j + i] == 1 || dr[i - j + N - 1] == 1){
      continue;
    }
    
    // i行目のj列にコマを置く(i列目はj列目のコマに襲撃されている)
    row[i] = j;
    // j行目, 左下方向, 右下方向にフラグを立てる.
    col[j] = dl[j+i] = dr[i-j+N-1] = 1;
    // i+1行目を探索
    solve(i+1);
    // フラグを解除する
    col[j] = dl[j+i] = dr[i-j+N-1] = -1;
  }
  
}

void init(){
  rep(i, N){
    row[i] = col[i] = -1;    
  }

  rep(i, 2*N-1){
    dl[i] = dr[i] = -1;
  }

  rep(i, N){
    rep(j, N){
      isLocated[i][j] = false;
    }
  }
}

signed main(){
  int n;
  int r, c;

  init();
  cin >> n;
  rep(i, n){
    cin >> r >> c;
    isLocated[r][c] = true;
  }
  solve(0);  
}

なんかバグらせまくって辛かった.