首页 > 专题系列 > Java解POJ > POJ 2243 Knight Moves [解题报告] Java
2013
11-10

POJ 2243 Knight Moves [解题报告] Java

Knight Moves

问题描述 :

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.

Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

输入:

The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

输出:

For each test case, print one line saying “To get from xx to yy takes n knight moves.”.

样例输入:

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

样例输出:

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

解题代码:

import java.util.*;
public class Main {

 private static int[][] position = new int[8][2];
 private static int[][] chessboard = new int[8][8];

 public Main() {
  initPosition();
 }

 /**
  * 初始化马可以走的方向
  */
 private static void initPosition() {
  position[0][0] = -2;
  position[0][1] = -1;
  position[1][0] = -2;
  position[1][1] = 1;
  position[2][0] = -1;
  position[2][1] = -2;
  position[3][0] = -1;
  position[3][1] = 2;
  position[4][0] = 1;
  position[4][1] = -2;
  position[5][0] = 2;
  position[5][1] = -1;
  position[6][0] = 1;
  position[6][1] = 2;
  position[7][0] = 2;
  position[7][1] = 1;
 }

 private static int[] getRC(String s) {
  int[] rc = new int[2];
  rc[0] = Integer.valueOf(String.valueOf(s.charAt(1))) - 1;
  rc[1] = s.charAt(0) - 'a';
  return rc;
 }

 /**
  * 广度搜索算法
  * 
  * @param s1
  * @param s2
  */
 public static void bsf(String s1, String s2) {
  int[] rc = getRC(s1);
  int formR = rc[0];
  int formC = rc[1];
  // System.out.println(formR + " ," + formC);
  rc = getRC(s2);
  int toR = rc[0];
  int toC = rc[1];
  // System.out.println(toR + " ," + toC);
  LinkedList< Point> queue = new LinkedList();

  Point p = new Point();
  p.r = formR;
  p.c = formC;
  p.steps = 0;
  queue.addLast(p);
  chessboard[p.r][p.c] = 1;
  p = null;

  while (!queue.isEmpty()) {
   p = queue.getFirst();
   queue.removeFirst();
   if (p.r == toR && p.c == toC) {
    System.out.println("To get from " + s1 + " to " + s2
      + " takes " + p.steps + " knight moves.");
    break;
   }
   for (int i = 0; i < 8; ++i) {
    Point pp = new Point();
    pp.r = p.r + position[i][0];
    pp.c = p.c + position[i][1];
    pp.steps = p.steps + 1;
    if (pp.r >= 0 && pp.c >= 0 && pp.r <= 7 && pp.c <= 7
      && chessboard[pp.r][pp.c] == 0) {
     queue.addLast(pp);
     chessboard[pp.r][pp.c] = 1;
    }
    pp = null;
   }
   p = null;
  }
 }

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  initPosition();
  while (sc.hasNext()) {
   chessboard = null;
   chessboard = new int[8][8];
   String s1 = sc.next();
   String s2 = sc.next();
   Main.bsf(s1, s2);
  }
 }

}

class Point {
 int r;
 int c;
 int steps;
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. [email protected]

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。