poj1915 广度优先遍历

问题重述：
背景
神话般的国际象棋玩家Somurolov先生，他声称，他可以把一个骑士从一个位置很快地移动到另一个位置，但其他人却不行。你能打败他吗？
存在的问题
你的任务是编写一个程序来计算的骑士达到从另一个位置所要移动的最少步数，这样你才有机会比Somurolov快。
也许人们不熟悉的国际象棋，骑士行动可能在如图1所示。

输入
首先在第一个行，输入n，表示有n种的情况。
接下来是n方案。每个方案包括三行。第一行指定一个棋盘边长L（4<=L<= 300）。整个棋盘的尺寸L *L.第二和第三行包含整数对（0，...，L - 1）*（0，...，L - 1）指定骑士开始和结束位置。整数对由一个空白分隔开。
输出
对于每个输入你要计算骑士的行动，有必要从起点移动到终点最少步数的情况。如果起点和终点都是平等的，距离是零。
2.解题过程：
分析过程：
当读懂了题意后，发现这可能是一道最短路径的应用，但当看到图算法的题目后，再仔细想下，这是一道广度优先遍历的应用，利用广搜去求最短路径比较简单。采用广度优先去搜索，一旦找到了就可以由搜索的深度去求出所需的最少步数。而广度优先的算法要用到队列，平时也做过练习，所以在算法上也就没有什么问题。而这道题的数据的输入问题，相对挺简单的。但存储就有点麻烦，因为棋盘的大小是从4*4到300*300，跨度比较大，如果只是定义最大的二维数组来存储，可能会浪费很多空间，此外，队列要存储的是一个棋盘的格子，所以要存至少两个数，为了方便，我直接使用两个整型的队列存储两个下标，感觉不难。
编程过程：
到了具体编程时，我才发现，如何由搜索的深度去求出所需的最少步数，这一步的实现挺麻烦的。我之前打算直接用以前写过的int型队列难以实现，除了要记录棋格的x,y坐标，还要记录棋格的步数。要不就只能重新定义一个新的结构体的队列，要不就得多个队列并行使用，但两者都挺麻烦的。所以我就想到如果我C++里有直接的队列可以使用，但我不会C++。最后发现poj上是可以提交java代码的，再想到下学期我得考sun的scjp认证，得复习下java。所以，最后打算用java来做。于是，我很快就用java把代码编出来了，自己测试也通过了，但提交时却说内存溢出。想了很久后，就大概猜到是什么原因，最初我是在得到size后就把整张棋盘都建了出来。这样就产生了很多的对象，自然多了许多没有用的对象霸占了许多内存。之后我就改为当需要时才去建棋格子的对象，果然少占了很多内存。但提交时，却发现运行错误，可是我自己测试却没问题，所以郁闷了很久。最后，发现有的地方会出现空指针异常，终于通过了。
3.做题收获：
通过这一道题，我找到了一个既可以练习java，又可以学到算法的途径，以后要多用java到poj上刷题才行。此外，我对java中的内存分配机制，有了更多的理解。题目虽然是通过了，但跟那些以前通过的人相比，我占用的内存还是太多了，这方面有待加强。用java做了题目后，我发现用C和java写代码，虽然用的算法是一样的，但对数据的输入与存储处理都有各自的优缺点。
程序源码

package middle;


import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Scanner;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 * poj1915最初做这道题时，我是就c去做的，但到了具体编程时，我发现有些地方要用到
 * 自定义类型的队列，自己去重写那些队列显行太麻烦了，本来C++就有现成的queue可以
 * 用，但我没学过c++，所以就想到用java。代码也很快就写了出来，但提交时却说内存溢出
 * 想了很久后，就大概猜到是什么原因，最初我是在得到size后就把整张棋盘都建了出来。
 * 这样就产生了很多的对象，自然多了许多没有用的对象霸占了许多内存。之后我就改为
 * 当需要时才去建棋格子的对象，果然少了很多内存。最后终于通过了。不过跟那些以前通过
 * 的人相比，我占用的内存还是太多了。
 * @author NC
 */
public class Poj1915 {

    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<chessNode> 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();//棋盘大小为size*size
            startX = scanner.nextInt();//初始位置x坐标
            startY = scanner.nextInt();//初始位置y坐标
            endX = scanner.nextInt();//目的位置x坐标
            endY = scanner.nextInt();//目的位置y坐标
            chessNode[][] chessPanel = new chessNode[size][size];
            //设置目的位置true
            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;
    }
}