ccbeginner

UVa Q11195

Feb 1st, 2020
55
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q11195
  2. //n queen problem
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int n;
  7. int maze[20];
  8. int ans;
  9. bool ok;
  10.  
  11. void dfs(int depth, int col, int rsh, int lsh){//depth := row
  12.     if(depth == n)++ans;
  13.     else{
  14.         int avail = ((1<<n) - 1) & ~col & ~rsh & ~lsh & maze[depth];
  15.         while(avail){
  16.             int lowbit = avail & -avail;
  17.             avail ^= lowbit;
  18.             dfs(depth+1, col | lowbit, (rsh | lowbit) >> 1, (lsh | lowbit) << 1);
  19.             if(!ok)return;
  20.         }
  21.     }
  22. }
  23.  
  24. int main(){
  25.     int cnt = 0;
  26.     while(cin >> n){
  27.         if(n == 0)break;
  28.         ok = 1;
  29.         ans = 0;
  30.         for(int i = 0; i < n; ++i){
  31.             maze[i] = (1<<n)-1;
  32.             for(int j = 0; j < n; ++j){
  33.                 char c;
  34.                 cin >> c;
  35.                 if(c == '*')maze[i] ^= (1<<j);
  36.             }
  37.         }
  38.         if(ok)dfs(0,0,0,0);
  39.         cout << "Case " << ++cnt << ": " << ans << endl;
  40.     }
  41.     return 0;
  42. }
RAW Paste Data