首页 > 专题系列 > Java解POJ > POJ 1657 Distance on Chessboard [解题报告] Java
2013
11-10

POJ 1657 Distance on Chessboard [解题报告] Java

Distance on Chessboard

问题描述 :

国际象棋的棋盘是黑白相间的8 * 8的方格,棋子放在格子中间。如下图所示:



王、后、车、象的走子规则如下:
  • 王:横、直、斜都可以走,但每步限走一格。
  • 后:横、直、斜都可以走,每步格数不受限制。
  • 车:横、竖均可以走,不能斜走,格数不限。
  • 象:只能斜走,格数不限。

写一个程序,给定起始位置和目标位置,计算王、后、车、象从起始位置走到目标位置所需的最少步数。

输入:

第一行是测试数据的组数t(0 <= t <= 20)。以下每行是一组测试数据,每组包括棋盘上的两个位置,第一个是起始位置,第二个是目标位置。位置用"字母-数字"的形式表示,字母从"a"到"h",数字从"1"到"8"。

输出:

对输入的每组测试数据,输出王、后、车、象所需的最少步数。如果无法到达,就输出”Inf”.

样例输入:

2
a1 c3
f5 f8

样例输出:

2 1 2 1
3 1 1 Inf

解题代码:

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
        int num = Integer.valueOf(cin.nextLine()).intValue();   
        String[] str = new String[2];   
        String a, b;   
        int x1, y1, x2, y2 = 0;   
        int kr, qr, cr, xr = 0;   
           
        for(int i = 0; i < num; i++)   
//      while(cin.hasNext())   
        {   
            str = cin.nextLine().split(" ");   
            a = str[0];   
            b = str[1];   
            x1 = convert(a.charAt(0));   
            y1 = Integer.valueOf(a.substring(1)).intValue();   
            x2 = convert(b.charAt(0));   
            y2 = Integer.valueOf(b.substring(1)).intValue();               
               
            if(x1==x2 && y1==y2)   
            {   
                System.out.println("0 0 0 0");   
                continue;   
            }   
                   
               
            kr = King(x1, y1, x2, y2);   
            qr = Queen(x1, y1, x2, y2);   
            cr = Che(x1, y1, x2, y2);   
            xr = Xiang(x1, y1, x2, y2);   
            System.out.print(kr + " "    
                    + qr + " " + cr + " ");   
            if(xr == -1)   
                System.out.println("Inf");   
            else  
                System.out.println(xr);   
        }   
  
    }   
       
    private static int convert(char x)   
    {   
        return x-96;   
    }   
  
    private static int King(int x1, int y1, int x2, int y2)   
    {   
        int x = Math.abs(x1 - x2);   
        int y = Math.abs(y1 - y2);   
        if(x > y)   
            return x;   
        else  
            return y;   
    }   
       
    private static int Queen(int x1, int y1, int x2, int y2)   
    {   
        if(x1 == x2 || y1 == y2)   
            return 1;   
        if(directCon(x1, y1, x2, y2) == true)   
            return 1;   
        else  
            return 2;   
    }   
       
    private static int Che(int x1, int y1, int x2, int y2)   
    {   
        if(x1 == x2 || y1 == y2)   
            return 1;   
        else  
            return 2;   
    }   
       
    private static boolean directCon(int x1, int y1, int x2, int y2)   
    {   
        if((x1+y1) == (x2+y2))   
            return true;   
        if((x1-x2) == (y1-y2))   
            return true;   
        return false;   
    }   
       
    private static int Xiang(int x1, int y1, int x2, int y2)   
    {   
        if((x1 + y1)%2 != (x2 + y2)%2)   
            return -1;   
        if(directCon(x1, y1, x2, y2) == true)   
            return 1;   
        return 2;   
    }   
  
}

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