//作为一个C过来人，要改成用java来写，前期真的有点难受的，所以：还是好好学吧
题目是这样的：
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
-
这有一个迷宫，有0~8行和0~8列：
1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,10表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）
- 输入
- 第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。 - 输出
- 输出最少走几步。
- 样例输入
-
2 3 1 5 7 3 1 6 7
- 样例输出
-
12 11
这道题目，说真的，用C++一点都不难，我可以几分钟之内把它写出来，但是改成java,我却凉凉了......
实在是不懂得，java中队列的实现啊。
看了别人的博客，才知道才懂得，java真的是虐我千万遍啊。。。。
Queue<类型> que = new LinkedList<Point>();
这是用java中包装好的类，来实现的，
如Queue<int> que = new LinkedList<Point>();
其中两个队列是经常用到的，que.offer(内容)，往队列末尾中添加元素。
que.poll()取出第一个元素，并它从队列中删除。
，，
不废话，看代码吧
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point
{
int x;
int y;
int step;
}
public class Main
{
static final int MAX = 9;
static int arr[][] = new int[][]{{1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,1,0,1},{1,0,0,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1},{1,0,0,0,0,1,0,0,1},{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},{ 1,1,0,1,0,0,0,0,1},{ 1,1,1,1,1,1,1,1,1}};
static Point start,end;
static final int N = 4;
static int X[] = new int[N];
static int Y[] = new int[N];
public static void main(String[] args)
{
init();
int n;
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
start = new Point();
end = new Point();
for(int i = 0 ; i < n ; i++)
{
start.x = cin.nextInt();
start.y = cin.nextInt();
start.step = 0;
end.x = cin.nextInt();
end.y = cin.nextInt();
if(start.x == end.x && start.y == end.y)
{
System.out.print(0 + " ");
continue;
}
BFS();
}
}
static void BFS()
{
Queue<Point> que = new LinkedList<Point>();
boolean mark[][] = new boolean[MAX][MAX];
for(int i = 0 ; i < MAX ; i++)
{
for(int j = 0 ; j < MAX ; j++)
{
mark[i][j] = false;
}
}
que.offer(start);
mark[start.x][start.y] = true;
while(!que.isEmpty())
{
Point z = new Point();
z = que.poll();
for(int i = 0 ; i < N ; i++)
{
Point k = new Point();
k.x = z.x + X[i];
k.y = z.y + Y[i];
k.step = z.step+1;
if(k.x >= 0 && k.x < MAX && k.y >= 0 && k.y < MAX && mark[k.x][k.y] == false && arr[k.x][k.y] == 0)
{
if(k.x == end.x && k.y == end.y)
{
System.out.print(k.step + " ");
return;
}
que.offer(k);
}
}
}
}
static void init()
{
X[0] = 1;
X[1] = -1;
X[2] = X[3] = 0;
Y[0] = Y[1] = 0;
Y[2] = -1;
Y[3] = 1;
}
}
注意，要考虑起始点和结束点是同一点的情况，不考虑，就会超时。