学步园

最少步数

描述

这有一个迷宫，有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,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
3 1  5 7
3 1  6 7

样例输出

12
11

来源

[苗栋栋]原创

上传者

苗栋栋

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

public class LeastStep {

    public
static void main(String[] args) {
   
    LeastStep
leastStep = new LeastStep();
   
   
leastStep.solution();
    }

    public void
solution() {
   
    Scanner in =
new Scanner(System.in);
   
    int[][] maze
= { { 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 } };
   
    int size =
in.nextInt();
   
    for (int j =
0; j < size; j++) {
   
   
    int startx =
in.nextInt();
   
   
    int starty =
in.nextInt();
   
   
    int endx =
in.nextInt();
   
   
    int endy =
in.nextInt();
           

   
   
    if(startx ==
endx && starty == endy){
   
   
   
   
System.out.println(0);
   
   
   
   
continue;
   
   
    }
   
   
    //
将矩阵复位
   
   
    for (int k =
0; k < 9; k++) {
   
   
   
    for (int h =
0; h < 9; h++) {
   
   
   
   
    if
(maze[k][h] < 0) {
   
   
   
   
   
    maze[k][h] =
0;