2014
12-12

### Problem

Given an arranged chess board with pieces, figure out the total number of different ways in which any piece can be killed in one move. Note: in this problem, the pieces can be killed despite of the color.

For example, if there are 3 pieces King is at B2, Pawn at A1 and Queen at H8 then the total number of pieces that an be killed is 3. H8-Q can kill B2-K, A1-P can kill B2-K, B2-K can kill A1-P

A position on the chess board is represented as A1, A2… A8,B1.. H8

Pieces are represented as

• (K) King can move in 8 direction by one place.
• (Q) Queen can move in 8 direction by any number of places, but can’t overtake another piece.
• (R) Rook can only move vertically or horitonzally, but can’t overtake another piece.
• (B) Bishop can only move diagonally, but can’t overtake another piece.
• (N) Knights can move to a square that is two squares horizontally and one square vertically OR one squares horizontally and two square vertically.
• (P) Pawn can only kill by moving diagonally upwards (towards higher number i.e. A -> B, B->C and so on).

### Input

The first line of the input gives the number of test cases, TT Test cases follow. Each test case consists of the number of pieces , NN lines follow, each line mentions where a piece is present followed by - with the piece type

### Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the the total number of different ways in which any piece can be killed.

### Limits

1 ≤ T ≤ 100.

#### Small dataset

1 ≤ N ≤ 10.
Pieces can include K, P

1 ≤ N ≤ 64.

### Sample Input

2
2
A1-K
A8-Q

3
B2-K
A1-P
H8-Q

Sample Output

Case #1: 1
Case #2: 3

/**
* Created by GaoTong on 2014/11/9.
*/
public class P4 {
static Scanner s = null;
//棋盘
static int map[][];
static int indexs[] = new int[256];
//简单的hash映射棋子的类型
static {
indexs['K'] = 1;indexs['Q'] = 2;indexs['R'] = 3;indexs['B'] = 4;indexs['N'] = 5;indexs['P'] = 6;
}
//棋子可走的方向
static int dirs[][][] = {
{},
{{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}},
{{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}},
{{0,1},{1,0},{0,-1},{-1,0}},
{{1,-1},{-1,1},{-1,-1},{1,1}},
{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{-1,-2},{1,-2}},
{{1,-1},{1,1}}

};
//棋子可走的距离
static int moves[] = {0,1,7,7,7,1,1,1};
public static void main(String args[]) throws FileNotFoundException {
int c = s.nextInt();

OutputStream os = new FileOutputStream(new File("C:\\Users\\admin\\IdeaProjects\\JavaLearn\\data\\D-large.out"));
PrintWriter pw = new PrintWriter(os);

for (int k = 1; k <= c; k++) {
map = new int[8][8];
int n = s.nextInt();
int positions[][] = new int[n][2];
for(int i=0; i<n ; i++){
String str = s.next();
positions[i][0] = str.charAt(0)-'A';
positions[i][1] = str.charAt(1)-'1';
map[positions[i][0]][positions[i][1]] = indexs[str.charAt(3)];
}
int sum = 0;
for(int i=0; i<n; i++){
sum += compute(positions[i][0],positions[i][1]);
}
System.out.println( "Case #" + k+": " +sum);
pw.println("Case #" + k+": " +sum);

}
pw.flush();;
pw.close();

}

static boolean checkxy(int x,int y){
return x>=0 && x<map.length && y >=0 && y<map.length;
}

//计算位置（x,y）的棋子，有多少种走法可以吃掉其它棋子
static  int compute(int x,int y){
int cnt = 0;
int player = map[x][y];
int dir[][] = dirs[player];
for(int i=0; i<dir.length; i++){
for(int len=1; len<=moves[player]; len++){
int nextx = x + len*dir[i][0];
int nexty = y + len*dir[i][1];
if(checkxy(nextx, nexty)){
if(map[nextx][nexty] > 0){
cnt++;
break;
}
}else{
break; //越界
}
}
}
return cnt;
}
}

1. ꔐ高仿 DKNY(唐可娜儿)Victoria Beckham(维多利亚·贝克汉姆)Hanmengli（韩梦丽）Gucci(古奇)柯马呢柯DIESEL(迪赛)yuandan.tk

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

4. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

5. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.