算法3.1—深度优先搜索

P1219 [USACO1.5] 八皇后 Checker Challenge

#include 
using namespace std;
typedef long long ll;
int n, l[50], r[50], vis[50], a[50];

int ans;
void dfs(int x){

if(x > n){

if(ans < 3)for(int i = 1; i <= n; i++)cout << a[i] << ' ';

if(ans < 3)cout << '\n';

ans++;

}

for(int i = 1; i <= n; i++){

if(l[i + x] || r[i - x + n] || vis[i])continue;

l[i + x] = r[i - x + n] = vis[i] = 1;

a[x] = i;

dfs(x + 1);

l[i + x] = r[i - x + n] = vis[i] = 0;

}

}
void solve() {

cin >> n;

dfs(1);

cout << ans;

}
int main() {

ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int _ = 1; //cin >> ;

while(--) solve();

return 0;

}