【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); }
なんかバグらせまくって辛かった.