Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///====================== TEMPLATE STARTS HERE =====================///
- #include <bits/stdc++.h>
- using namespace std;
- //#include <ext/pb_ds/assoc_container.hpp> // Include for built in treap
- //#include <ext/pb_ds/tree_policy.hpp>
- //using namespace __gnu_pbds;
- //#include <sys/resource.h> // for linux stack memory increase
- //#define gc getchar_unlocked // for linux fast io
- //#define gc getchar // for windows fast io
- #define pb push_back
- #define MP make_pair
- #define ff first
- #define ss second
- #define nl puts("")
- #define sp printf(" ")
- #define phl debug("Hello")
- #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
- #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
- #define CLR(x,y) memset(x,y,sizeof(x))
- #define ALL(x) (x).begin(),(x).end()
- #define SZ(x) ((vlong)(x).size())
- #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
- #define MIN(a,b) ((a)<(b)?(a):(b))
- #define MAX(a,b) ((a)>(b)?(a):(b))
- #define ABS(x) ((x)<0?-(x):(x))
- #define FABS(x) ((x)+eps<0?-(x):(x))
- #define SQ(x) ((x)*(x))
- #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
- #define POPCOUNT __builtin_popcountll
- #define RIGHTMOST __builtin_ctzll
- #define LEFTMOST(x) (63-__builtin_clzll((x)))
- #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
- #define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
- #define ODD(x) (((x)&1)==0?(0):(1))
- #define Set(N,p) N=((N)|((1LL)<<(p)))
- #define Reset(N,p) N=((N)&(~((1LL)<<(p))))
- #define Check(N,p) (!(((N)&((1LL)<<(p)))==(0)))
- #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
- #define arrayIndexPrint(A,i) cerr<<"~ At pos: "<<i<<" = "<<A[i]
- #define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
- #define arrayPrint(A,st,ed) cerr<<"~ Array:";FOR(i,st,ed) cerr<<" "<<A[i];cerr<<endl
- #define LINE cerr<<"\n"; FOR(i,0,50) cerr<<"=";cerr<<"\n\n"
- #define LL long long
- #define LLU long long unsigned int
- typedef long long vlong;
- typedef unsigned long long uvlong;
- typedef pair < int, int > pii;
- typedef pair < vlong, vlong > pll;
- typedef vector<int> vi;
- typedef vector<vlong> vl;
- typedef vector<pll> vll;
- //typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_ds;
- #ifdef forthright48
- #include <ctime>
- clock_t tStart = clock();
- #define debug(args...) {dbg,args; cerr<<endl;}
- #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
- #define bug printf("%d\n",__LINE__);
- #else
- #define debug(args...) // Just strip off all debug tokens
- #define timeStamp
- #endif
- struct debugger{
- template<typename T> debugger& operator , (const T& v){
- cerr<<v<<" ";
- return *this;
- }
- }dbg;
- inline vlong gcd ( vlong a, vlong b ) {
- a = ABS ( a ); b = ABS ( b );
- while ( b ) { a = a % b; swap ( a, b ); } return a;
- }
- vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
- vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
- x2 = 1; y2 = 0;
- x1 = 0; y1 = 1;
- for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
- q = r2 / r1;
- r = r2 % r1;
- x = x2 - (q * x1);
- y = y2 - (q * y1);
- }
- *X = x2; *Y = y2;
- return r2;
- }
- inline vlong modInv ( vlong a, vlong m ) {
- vlong x, y;
- ext_gcd( a, m, &x, &y );
- x %= m;
- if ( x < 0 ) x += m;
- return x;
- }
- inline vlong bigmod ( vlong a, vlong p, vlong m ) {
- vlong res = 1 % m, x = a % m;
- while ( p ) {
- if ( p & 1 ) res = ( res * x ) % m;
- x = ( x * x ) % m; p >>= 1; /// For bigmod2 multiply here using mulmod
- }
- return res;
- }
- //int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
- //int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
- //int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
- const vlong inf = 2147383;
- const vlong mod = 1000000007;
- const double pi = 2 * acos ( 0.0 );
- const double eps = 1e-11;
- ///====================== TEMPLATE ENDS HERE =====================///
- struct chess{
- int row[8], col[8];
- };
- vector<chess> List; /// List of all valid chess states
- string mat[8];
- /// Check if i place a queen at (r,c) then will it clash
- /// with previous queens.
- bool clash(chess &cur, int r, int c){
- FOR(i,0,r-1){
- if(cur.col[i] == c) return true;
- if(ABS(r-cur.row[i]) == ABS(c-cur.col[i])) return true;
- }
- return false;
- }
- /// Find all possible valid states
- void backtrack(int r, chess &cur){
- if(r == 8){
- List.pb(cur);
- return;
- }
- FOR(c,0,7){
- if(clash(cur, r, c)) continue;
- cur.row[r] = r;
- cur.col[r] = c;
- backtrack(r+1, cur);
- }
- }
- int DP[(1<<8)+50];
- int moveCount(chess &src, int q1, chess &trg, int q2){
- int r1 = src.row[q1], c1 = src.col[q1];
- int r2 = trg.row[q2], c2 = trg.col[q2];
- if(r1==r2 && c1==c2) return 0; /// Same cell
- if(r1==r2 || c1 == c2) return 1; /// Same row/col
- if(ABS(r1-r2) == ABS(c1-c2)) return 1; /// Same diagonal
- return 2;
- }
- int call(int mask, chess &src, chess &trg){
- int q1 = POPCOUNT(mask);
- if(q1 == 8) return 0;
- if(DP[mask] != -1) return DP[mask];
- int res = inf;
- FOR(q2,0,7){
- if(Check(mask, q2)) continue;
- int nmask = mask;
- Set(nmask, q2);
- int ret = call(nmask, src, trg) + moveCount(src, q1, trg, q2);
- res = min(res, ret);
- }
- return DP[mask] = res;
- }
- chess buildChess(){
- chess cur;
- int q = 0;
- FOR(r,0,7){
- FOR(c,0,7){
- if(mat[r][c] == 'q'){
- cur.row[q] = r, cur.col[q] = c;
- q++;
- }
- }
- }
- return cur;
- }
- int main () {
- #ifdef forthright48
- freopen ( "input.txt", "r", stdin );
- //freopen ( "output.txt", "w", stdout );
- #endif // forthright48
- fast_cin;
- chess cur;
- backtrack(0, cur);
- int t;
- cin >> t;
- FOR(cs,1,t){
- FOR(i,0,7){
- cin >> mat[i];
- }
- chess src = buildChess();
- int res = inf;
- FOR(i,0,SZ(List)-1){
- CLR(DP, -1);
- int ret = call(0, src, List[i]);
- res = min(res, ret);
- }
- printf("Case %lld: %d\n",cs,res);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement