Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //UVa Q11195
- //n queen problem
- #include <bits/stdc++.h>
- using namespace std;
- int n;
- int maze[20];
- int ans;
- bool ok;
- void dfs(int depth, int col, int rsh, int lsh){//depth := row
- if(depth == n)++ans;
- else{
- int avail = ((1<<n) - 1) & ~col & ~rsh & ~lsh & maze[depth];
- while(avail){
- int lowbit = avail & -avail;
- avail ^= lowbit;
- dfs(depth+1, col | lowbit, (rsh | lowbit) >> 1, (lsh | lowbit) << 1);
- if(!ok)return;
- }
- }
- }
- int main(){
- int cnt = 0;
- while(cin >> n){
- if(n == 0)break;
- ok = 1;
- ans = 0;
- for(int i = 0; i < n; ++i){
- maze[i] = (1<<n)-1;
- for(int j = 0; j < n; ++j){
- char c;
- cin >> c;
- if(c == '*')maze[i] ^= (1<<j);
- }
- }
- if(ok)dfs(0,0,0,0);
- cout << "Case " << ++cnt << ": " << ans << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment