首页 > 基础算法 > 模拟法 > Problem D.Itz Chess-Google apac
2014
12-12

Problem D.Itz Chess-Google apac

题目链接:http://code.google.com/codejam/contest/6214486/dashboard#s=p3

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

Large dataset

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.
 * copyright: www.acmerblog.com
 */
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 {
        s = new Scanner(new File("C:\\Users\\admin\\IdeaProjects\\JavaLearn\\data\\D-large.in"));
        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. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

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

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

  4. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样: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();}.