首页 > 其他 > 详细

少转弯问题

时间:2020-02-24 16:59:55      阅读:61      评论:0      收藏:0      [点我收藏+]

给出一张地图,这张地图被分为n×m(n,m<=100)个方块,任何一个方块不是平地就是高山。平地可以通过,高山则不能。现在你处在地图的(x1,y1)这块平地,问:你至少需要拐几个弯才能到达目的地(x2,y2)?你只能沿着水平和垂直方向的平地上行进,拐弯次数就等于行进方向的改变(从水平到垂直或从垂直到水平)的次数。例如:如图,最少的拐弯次数为5。

技术分享图片

输入格式

第1行:n m

第2至n+1行:整个地图地形描述(0:空地;1:高山),

如(图)第2行地形描述为:1 0 0 0 0 1 0

第3行地形描述为:0 0 1 0 1 0 0

第n+2行:x1 y1 x2 y2 (分别为起点、终点坐标)

输出格式

s (即最少的拐弯次数)

样例输入

5 7

1 0 0 0 0 1 0

0 0 1 0 1 0 0

0 0 0 0 1 0 1

0 1 1 0 0 0 0

0 0 0 0 1 1 0

1 3 1 7

样例输入

5

import java.util.ArrayList;
import java.util.Scanner;

public class test {
        //王耀辉
    static Scanner sc=new Scanner(System.in);
    //n为长   m为宽     a为地图信息   b为记录点是否走过    l为记录走的点得坐标    min找的得最小值    fang为方向数组
    static int n=sc.nextInt();
    static int m=sc.nextInt();
    static int [][]a=new int[n][m];
    static boolean [][]b=new boolean[n][m];
    static ArrayList<Integer> l=new ArrayList<Integer>();
    static int []fang={-1,0,1,0,0,-1,0,1};
    static int min=Integer.MAX_VALUE;
public static void main(String[] args) {
    //存入地图信息
    for (int i = 0; i <n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j]=sc.nextInt();
        }
    }
    //x1,y1起点坐标    x2,y2终点坐标
    int x1=sc.nextInt()-1;
    int y1=sc.nextInt()-1;
    int x2=sc.nextInt()-1;
    int y2=sc.nextInt()-1;
    l.add(x1);
    l.add(y1);
    b[x1][y1]=true;
    f(x1,y1,x2,y2);
    System.out.println(min);
}
private static void f(int x1, int y1, int x2, int y2) {
    // TODO Auto-generated method stub
    if (x1==x2&&y1==y2) {
        //存我现在走得方向
        int []fang1=new int[2];
        //记录我转了几次
        int ji=0;
        //循环我的路线集合
        for (int i = 2; i <l.size()-2; i+=2) {
            //判断我这步走的方向是否和下一步走的一样
            if (l.get(i)+fang1[0]==l.get(i+2)&&l.get(i+1)+fang1[1]==l.get(i+3)) {
                continue;
            }else {
                //更改方向
                fang1[0]=l.get(i+2)-l.get(i);
                fang1[1]=l.get(i+3)-l.get(i+1);
                ji++;
            }
        }
        //找到最小值
        if (ji<min) {
            min=ji;
        }
    }else {
        for (int i = 0; i < fang.length; i+=2) {
            //接下来要走得坐标
            int x=x1+fang[i];
            int y=y1+fang[i+1];
            //判断接下来是否越界 和  接下来是否走过     接下来走的是否是平原
            if (x>=0&&x<n&&y>=0&&y<m&&!b[x][y]&&a[x][y]==0) {
                x1+=fang[i];
                y1+=fang[i+1];
                b[x1][y1]=true;
                l.add(x1);
                l.add(y1);
                f(x1,y1,x2,y2);
                b[x1][y1]=false;
                x1-=fang[i];
                y1-=fang[i+1];
                l.remove(l.size()-1);
                l.remove(l.size()-1);
            }
        }
    }
}
}

 

少转弯问题

原文:https://www.cnblogs.com/shiaguang/p/12357547.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!