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

POJ 1915 Knight Moves [解题报告] Java

Knight Moves

问题描述 :

Background

Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?

The Problem

Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.

For people not familiar with chess, the possible knight moves are shown in Figure 1.

输入:

The input begins with the number n of scenarios on a single line by itself.

Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

输出:

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

样例输入:

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

样例输出:

5
28
0

解题代码:

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
public class Main {   
  
    private static int[][] directions = new int[][]{   
        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};   
  
    static void BreadthFirstSearch(int startX, int startY,   
            chessNode[][] chessPanel, int size) {   
        chessNode currentNode = null, nextNode = null;   
        LinkedList queue = new LinkedList();   
        currentNode = chessPanel[startY][startY] =   
                new chessNode(startX, startY, true, 0, false);   
        queue.addLast(currentNode);
        while (!queue.isEmpty()) {   
            currentNode = queue.removeFirst();
            if (currentNode.isTarget()) {  
                break;   
            }   
            for (int i = 0; i < 8; i++) {   
                int x = currentNode.getX() + directions[i][0];   
                int y = currentNode.getY() + directions[i][1];   
                int step = currentNode.getStep();   
                if (x >= 0 && x < size && y >= 0 && y < size) {   
                    if (chessPanel[x][y] == null) {   
                        chessPanel[x][y] = new chessNode(x, y, false, 0, false);   
                    }   
                    nextNode = chessPanel[x][y];   
                    if (!nextNode.isVisited()) {   
                        nextNode.setVisited(true);
                        nextNode.setStep(step + 1);   
                        queue.addLast(nextNode);   
                    }   
                }   
            }   
        }   
    }   
  
    public static void main(String[] args) {   
        int n = 0;   
        int size = 0;   
        int startX = 0, startY = 0, endX = 0, endY = 0;   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        n = scanner.nextInt();   
        for (int i = 0; i < n; i++) {   
            size = scanner.nextInt();   
            startX = scanner.nextInt();   
            startY = scanner.nextInt();
            endX = scanner.nextInt();
            endY = scanner.nextInt();
            chessNode[][] chessPanel = new chessNode[size][size];   
            chessPanel[endX][endY] = new chessNode(endX, endY, false, 0, true);   
            BreadthFirstSearch(startX, startY, chessPanel, size);   
            System.out.println(chessPanel[endX][endY].getStep());   
        }   
    }   
}   
  
class chessNode {   
  
    private int x;   
    private int y;   
    private boolean visited;
    private int step;
  
    public int getX() {   
        return x;   
    }   
  
    public chessNode(int x, int y, boolean visited, int step, boolean target) {   
        this.x = x;   
        this.y = y;   
        this.visited = visited;   
        this.step = step;   
        this.target = target;   
    }   
  
    public void setX(int x) {   
        this.x = x;   
    }   
  
    public int getY() {   
        return y;   
    }   
  
    public void setY(int y) {   
        this.y = y;   
    }   
    private boolean target;   
  
    public boolean isVisited() {   
        return visited;   
    }   
  
    public void setVisited(boolean visited) {   
        this.visited = visited;   
    }   
  
    public int getStep() {   
        return step;   
    }   
  
    public void setStep(int step) {   
        this.step = step;   
    }   
  
    public boolean isTarget() {   
        return target;   
    }   
  
    public void setTarget(boolean target) {   
        this.target = target;   
    }   
}

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

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

  4. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.