APAC 2014 round 4 D

#include<algorithm>
#include<bitset>
#include<cctype>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<iterator>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<strstream>
#include<string>
#include<utility>
#include<vector>
#include <cstdarg>
using namespace std;
/***************************************************************************************************************************************/
typedef long long int LLI;
typedef unsigned long long int ULLI;
#define MP(X,Y) make_pair(X,Y)

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define fill(a,v) memset(a,v,sizeof(a))
#define DEBUG(x) cout << #x << ": " << x << endl;
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define VI vector<int>
#define VS vector<string>
#define PB push_back
#define REV(a) reverse(all(a))
typedef pair<int, int>PII;


#define BRPS(n,bit) bitset<bit>(n)
template<class T> inline T BIGMOD(T n, T m, T mod)
{
    LLI ans = 1;
    LLI k = n;
    while(m)
    {
        if(m & 1)
        {
            ans *= k;
            if(ans>mod) ans %= mod;
        }
        k *= k;
        if(k>mod) k %= mod;
        m >>= 1;
    }
    return ans;
}
#define eps 1e-11
template<class T> string toString(T n)
{
    ostringstream ost;
    ost << n;
    ost.flush();
    return ost.str();
}
template<class T> string toBinary(T n)
{
    string ret="";
    while(n)
    {
        if(n%2==1)ret+='1';
        else ret+='0';
        n>>=1;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
void combination(int n,vector< vector<int> > &ret)
{
    ret.resize(n+1, vector<int>(n+1, 0));
    for(int i=1; i<=n; i++)
    {
        ret[i][0]=ret[i][i]=1;
        for(int j=1; j<i; j++)
        {
            ret[i][j]=ret[i-1][j]+ret[i-1][j-1];
        }
    }
}
int toInt(string s)
{
    int r = 0;
    istringstream sin(s);
    sin >> r;
    return r;
}
LLI toLInt(string s)
{
    LLI r = 0;
    istringstream sin(s);
    sin >> r;
    return r;
}
double toDouble(string s)
{
    double r = 0;
    istringstream sin(s);
    sin >> r;
    return r;
}
vector<string> parse(string temp)
{
    vector<string> ans;
    ans.clear();
    string s;
    istringstream iss(temp);
    while (iss >> s)ans.PB(s);
    return ans;
}
template<class T> inline T gcd(T a, T b)
{
    if (a < 0)return gcd(-a, b);
    if (b < 0)return gcd(a, -b);
    return (b == 0) ? a : gcd(b, a % b);
}
template<class T> inline T lcm(T a, T b)
{
    if (a < 0)return lcm(-a, b);
    if (b < 0)return lcm(a, -b);
    return a*(b / gcd(a, b));
}
template<class T> inline T power(T b, T p)
{
    if (p < 0)return -1;
    if (b <= 0)return -2;
    if (!p)return 1;
    return b*power(b, p - 1);
}

template<class T> inline int asd(T &ret)
{
    char r;
    bool start=false,neg=false;
    ret=0;
    while(true)
    {
        r=getchar();
        if(r==EOF)return 0;
        if((r-'0'<0 || r-'0'>9) && r!='-' && !start)
        {
            continue;
        }
        if((r-'0'<0 || r-'0'>9) && r!='-' && start)
        {
            break;
        }
        if(start)ret*=10;
        start=true;
        if(r=='-')neg=true;
        else ret+=r-'0';
    }

    if(neg)
        ret*=-1;
    return 1;
}

template<class T> inline void asdasd(T x,char y)
{
    // 0- print+newline, 1 - print ' ',2 - nothing;
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    char buf[21], *p = buf;
    do
    {
        *p++ = '0' + x % 10;
        x /= 10;
    }
    while (x);
    do
    {
        putchar(*--p);
    }
    while (p > buf);
    if(y==0)putchar('\n');
    else if(y==1)putchar(' ');
}
#define filein(x) freopen(x,"r",stdin)
#define fileout(x) freopen(x,"w",stdout)
#define fst first
#define snd second
//istringstream(temp) >> data >> value >> stamp;
//mod1 = 1000000007, mod2 = 1000000009;
//.016-.040-.900-2.48
/***************************************************************************************************************************************/

vector<PII>V;
int chess[70][70];
char P[]= {'K','Q','R','B','N','P'};
int Piece(char p)
{
    for(int i=0; i<6; i++)if(P[i]==p)return i;
}

int Grid(char x,char y,char pc)
{
    //if(pc!='K' && pc!='P')cout << "->" << pc << endl;
    chess[x-'A'][y-'1']=Piece(pc);
    V.PB(MP(x-'A',y-'1'));
}

char p,q,r;
int n;


bool CanKingGo(int px,int py,int qx,int qy)
{
    if(abs(px-qx)<=1 && abs(py-qy)<=1)return true;
    return false;
}

bool CanPawnGo(int px,int py,int qx,int qy)
{
    if(px+1==qx && abs(py-qy)==1)return true;
    return false;
}

bool CanRookGo(int px,int py,int qx,int qy)
{
    if(px!=qx && py!=qy)return false;
    if(px==qx)
    {
        if(py>qy)swap(py,qy);
        while(py<qy)
        {
            py++;
            if(py==qy)return true;
            if(chess[px][py]!=-1)return false;
        }
        return true;
    }
    else
    {
        if(px>qx)swap(px,qx);
        while(px<qx)
        {
            if(px==qx)return true;
            px++;
            if(chess[px][py]!=-1)return false;
        }
        return true;
    }
}
bool CanKnightGo(int px,int py,int qx,int qy)
{
    for(int i=-2;i<=2;i++)
    {
        for(int j=-2;j<=2;j++)
        {
            if((abs(i)==2 && abs(j)==1) || (abs(i)==1 && abs(j)==2))
            {
                if(px+i==qx && py+j==qy)return true;
            }
        }
    }
    return false;
}

bool CanBishopGo(int px,int py,int qx,int qy)
{
    if(abs(px-qx)!=abs(py-qy))return false;
    while(px!=qx)
    {

        if(px<qx)px++;
        else px--;
        if(py<qy)py++;
        else py--;
        if(px==qx)return true; // is this wrong?
        if(chess[px][py]!=-1)
        {
            return false;
        }
    }
    return true;
}
bool CanQueenGo(int px,int py,int qx,int qy)
{
    int a=CanRookGo(px,py,qx,qy);
    int b=CanBishopGo(px,py,qx,qy);
    return a||b ;
}
bool Take(int idx,int idy)
{
    int px,py,qx,qy;
    px=V[idx].fst;
    py=V[idx].snd;

    qx=V[idy].fst;
    qy=V[idy].snd;

    if(chess[px][py]==0)return CanKingGo(px,py,qx,qy);
    if(chess[px][py]==1)return CanQueenGo(px,py,qx,qy);
    if(chess[px][py]==2)return CanRookGo(px,py,qx,qy);
    if(chess[px][py]==3)return CanBishopGo(px,py,qx,qy);
    if(chess[px][py]==4)return CanKnightGo(px,py,qx,qy);
    if(chess[px][py]==5)return CanPawnGo(px,py,qx,qy);
}


int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-small-attempt0.in","r",stdin);
    //freopen("D-large.txt","w",stdout);
    int kase,ks=0;
    asd(kase);
    while(kase--)
    {
        fill(chess,-1);
        asd(n);
        V.clear();
        for(int i=0; i<n; i++)
        {
            p=getchar();
            q=getchar();
            getchar();
            r=getchar();
            getchar();
            Grid(p,q,r);
        }
        int res=0;
        for(int i=0;i<V.size();i++)
        {
            for(int j=0;j<V.size();j++)
            {
                if(i!=j && Take(i,j))
                {
                    res++;
                }
            }
        }
        printf("Case #%d: %d\n",++ks,res);
    }
    return 0;
}
/*
2
3
A1-N
C2-Q
C3-Q
3
B2-K
A1-P
H8-Q
*/