文档章节

Java算法--寻路

ChamPly
 ChamPly
发布于 2017/08/31 13:00
字数 1769
阅读 5
收藏 0
点赞 1
评论 0

题目:

要求用户输入一个值n作为一个n*n的矩阵大小,然后用户输入n行,每行有n个字符,每个字符用空格隔开,其中字符“A”表示起点,字符“B”表示终点,中间寻路有要求,如果当前字符是“+”则下一步必须是字符“-”或者字符“B”,如果当前字符是“-”则下一步必须是字符“+”或者字符“B”,如果当前字符是“A”则下一步是字符“+”字符“-”字符“B”都行。不考虑用户输入的其他字符,只有“+”“-”“B”,然后输出结果,能到达的最小的步数。

代码:

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

public class Main{
	
	//矩阵的大小
	static int n;
	//用于记录是否走到了终点,true表示到了,false表示没有到,默认false
	static boolean flag = false;
	//用于存放所有的结果
	static ArrayList<Integer> list = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.nextLine();
		
		String[][] map = Produce();
		
		//测试代码
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		
		//得到"A"的坐标,"B"的坐标
		int[] a = Local(map, "A");
		int[] b = Local(map, "B");
		
		//测试坐标是否正确
		System.out.println(a[0] + "   " + a[1]);
		System.out.println(b[0] + "   " + b[1]);
		
		//开始移动
		Move(map, a, b, 0);
		
		System.out.println("=========================");
		
		if(list.size() < 1){
			System.out.println("没有找到路径");
		}
		else{
			int mix = list.get(0);
			for(int i = 1; i < list.size(); i++){
				if(mix > list.get(i)){
					mix = list.get(i);
				}
			}
			System.out.println("最小路径为:" + mix);
		}
		
		//测试结束标志
		System.out.println("end!");
	}
	
	private static void Move(String[][] m, int[] a, int[] b, int s) {
		//用于记录走过的步数
		int sum = s;		
		String[][] map = m;
		//表示当前坐标
		int[] local = a;
		//表示终点坐标
		int[] end = b;
		
		MoveUp(map, local, end, sum);
		System.out.println(flag);
		//判断上一步是否到达了终点
		if(flag){
			//加入List集合,然后初始化,接着其他方案
			list.add(sum+1);
			flag = false;
		}
		
		//重新赋值
		sum = s;		
		map = m;
		local = a;
		end = b;			
		MoveRight(map, local, end, sum);
		System.out.println(flag);
		if(flag){
			//加入List集合,然后初始化,接着其他方案
			list.add(sum+1);
			flag = false;
		}
		
		//重新赋值
		sum = s;		
		map = m;
		local = a;
		end = b;
		MoveDown(map, local, end, sum);
		System.out.println(flag);
		if(flag){
			//加入List集合,然后初始化,接着其他方案
			list.add(sum+1);
			flag = false;
		}
		
		//重新赋值
		sum = s;		
		map = m;
		local = a;
		end = b;
		MoveLeft(map, local, end, sum);
		System.out.println(flag);
		if(flag){
			//加入List集合,然后初始化,接着其他方案
			list.add(sum+1);
			flag = false;
		}
		
	}

	private static void MoveLeft(String[][] map, int[] local, int[] end, int sum) {
//		//重新定义,用于保护现场,避免下一次走错
//		String[][] map = m;
//		int[] local = a;
//		int[] end = b;
//		int sum = s;
		
		//首先判断当前的坐标能不能向左移动
		if(local[1] != 0){
			//判断是否到了终点
			if((local[0] == end[0]) && (local[1]-1 == end[1])){
				//设置到达了终点
				flag = true;
//				return;
			}
			else{
				if(map[local[0]][local[1]].equals("A")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("+") && 
						map[local[0]][local[1]-1].equals("-")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("-") && 
						map[local[0]][local[1]-1].equals("+")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
			}
		}
		
	}

	private static void MoveDown(String[][] map, int[] local, int[] end, int sum) {
//		//重新定义,用于保护现场,避免下一次走错
//		String[][] map = m;
//		int[] local = a;
//		int[] end = b; 
//		int sum = s;
		
		//首先判断当前的坐标能不能向下移动
		if(local[0] != n-1){
			//判断是否到了终点
			if((local[0]+1 == end[0]) && (local[1] == end[1])){
				//设置到达了终点
				flag = true;
				return;
			}
			else{
				if(map[local[0]][local[1]].equals("A")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("+") && 
						map[local[0]+1][local[1]].equals("-")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("-") && 
						map[local[0]+1][local[1]].equals("+")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
			}
		}
		
	}

	private static void MoveRight(String[][] map, int[] local, int[] end, int sum) {
//		//重新定义,用于保护现场,避免下一次走错
//		String[][] map = m;
//		int[] local = a;
//		int[] end = b; 
//		int sum = s;
		
		//首先判断当前的坐标能不能向右移动
		if(local[1] != n-1){
			//判断是否到了终点
			if((local[0] == end[0]) && (local[1]+1 == end[1])){
				//设置到达了终点
				flag = true;
				return;
			}
			else{
				if(map[local[0]][local[1]].equals("A")){
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("+") && 
						map[local[0]][local[1]+1].equals("-")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("-") && 
						map[local[0]][local[1]+1].equals("+")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[1]++;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
			}
		}
		
	}

	private static void MoveUp(String[][] map, int[] local, int[] end, int sum) {
		
//		//重新定义,用于保护现场,避免下一次走错
//		String[][] map = m;
//		int[] local = a;
//		int[] end = b; 
//		int sum = s;
		
		//首先判断当前的坐标能不能向上移动
		if(local[0] != 0){
			//判断是否到了终点
			if((local[0]-1 == end[0]) && (local[1] == end[1])){
				//设置到达了终点
				flag = true;
				return;
			}
			else{
				if(map[local[0]][local[1]].equals("A")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("+") && 
						map[local[0]-1][local[1]].equals("-")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
				else if(map[local[0]][local[1]].equals("-") && 
						map[local[0]-1][local[1]].equals("+")){
					//把当前位置置为空,避免下一次重复走
					map[local[0]][local[1]] = " ";
					//改变坐标
					local[0]--;
					sum++;//步数加1
					//调用Move函数,接着往下走
					Move(map, local, end, sum);
				}
			}
		}
		
	}

	//得到str的坐标
	private static int[] Local(String[][] map, String str) {
		int[] local = new int[2];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(map[i][j].equals(str)){
					local[0] = i;
					local[1] = j;
					return local;
				}
			}
		}
		
		return local;
	}

	//产生一个n*n的阵列
	private static String[][] Produce(){
		Scanner sc = new Scanner(System.in);
		String[] m = new String[n];
		String[][] map = new String[n][n];
		
		//控制台输入
		for(int i = 0; i < n; i++){
			m[i] = sc.nextLine();
		}
		
		//对输入的数据进行转换成去掉空格的
		for(int i = 0; i < n; i++){
			map[i] = m[i].split(" ");
		}
		
		return map;
	}
}

2015年6月1日
by:champly 

© 著作权归作者所有

共有 人打赏支持
ChamPly

ChamPly

粉丝 11
博文 42
码字总数 32506
作品 0
朝阳
程序员
方向选择(嵌入式 大数据 java)

嵌入式:单片机之类的 比如指纹解锁底层就是此技术,反正就是和硬件打交道。 大数据:最近很火的概念技术 有点玄玄乎乎的,前途不好定义,不过门槛也是高的,对算法之类的要求还是比较高的 ...

codingcoge ⋅ 05/03 ⋅ 0

聊聊JAVA虚拟机中的垃圾收集器

前言 JAVA虚拟机的垃圾收集器是虚拟机内存的清道夫,它的存在让JAVA开发人员能将更多精力投入到业务研发上。了解垃圾收集器,并利用好这个工具,能更好的保障服务稳定性。这篇文章通过分析J...

lilugoodjob ⋅ 05/13 ⋅ 0

Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区 ⋅ 05/09 ⋅ 0

《成神之路-基础篇》JVM——垃圾回收(已完结)

Java内存模型,Java内存管理,Java堆和栈,垃圾回收 本文是[《成神之路系列文章》][1]的第一篇,主要是关于JVM的一些介绍。 持续更新中 Java之美[从菜鸟到高手演变]之JVM内存管理及垃圾回收 ...

⋅ 05/05 ⋅ 0

用大白话告诉你啥是Java开发

Java,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台的总称。用Java实现的HotJava浏览器(支持Java applet)显示了Java的魅力:跨平台、动态的Web、Internet计算。从此...

远方Java ⋅ 06/14 ⋅ 0

面试中关于Java虚拟机(jvm)的问题看这篇就够了

最近看书的过程中整理了一些面试题,面试题以及答案都在我的文章中有所提到,希望你能在以问题为导向的过程中掌握虚拟机的核心知识。面试毕竟是面试,核心知识我们还是要掌握的,加油~~~ 下面...

snailclimb ⋅ 05/12 ⋅ 0

热修复与插件化基础——Java与Android虚拟机

一、Java虚拟机(JVM) 1、JVM整体结构 使用javac将java文件编译成class文件。 类加载器(ClassLoader)将class字节码加载进JVM对应的内存中。 JVM将内存分配给方法区、堆区、栈区、本地方式...

CSDN_LQR ⋅ 05/13 ⋅ 0

新浪、百度、好未来3offer到手全记录 | 牛客面经

新浪、百度、好未来3offer到手全记录 牛客面经 原创 2017-09-19 牛友 招聘消息汇总 渣渣的秋招之路 附上新浪,百度,好未来面经 作者:offer快到碗里来?。! 来源:牛客网 楼主是本科渣渣,...

公子只识黛玉 ⋅ 04/17 ⋅ 0

阿里、百度等多家公司Java面试记录与总结

算算自己大概面试了近十家公司,也拿到了几个Offer,现在面试告一段落,简单总结下面试经验。 我现在主要的方向是Java服务端开发,把遇到的问题和大家分享一下,也谈谈关于技术人员如何有方向...

⋅ 02/24 ⋅ 0

安卓开发必备知识体系:Java篇

大家好我是张拭心,自从各位朋友帮点广X开始,我发现我每天更有奔头了,走起路来也更有劲了,说啥也得更新的勤快一点。不过放心,我一定推送有价值的内容给大家,还请朋友们照旧动动手指点点...

d29h1jqy3akvx ⋅ 05/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Greys Java在线问题诊断工具

Greys是一个JVM进程执行过程中的异常诊断工具。 在不中断程序执行的情况下轻松完成JVM相关问题排查工作 目标群体 有时候突然一个问题反馈上来,需要入参才能完成定位,但恰恰没有任何日志。回...

素雷 ⋅ 27分钟前 ⋅ 0

git从远程仓库拉取代码的常用指令

一种(比较麻烦的)拉代码的方法 git clone //克隆代码库,与远程代码库的主干建立连接,如果主干已经在就不用再clone啦,克隆路径为当前路径下的新创建的文件夹 git checkout -b //本地建立...

Helios51 ⋅ 41分钟前 ⋅ 0

005. 深入JVM学习—Java堆内存参数调整

1. JVM整体内存调整图解(调优关键) 实际上每一块子内存区域都会存在一部分可变伸缩区域,其基本流程:如果内存空间不足,则在可变的范围之内扩大内存空间,当一段时间之后,内存空间不紧张...

影狼 ⋅ 46分钟前 ⋅ 0

内存障碍: 软件黑客的硬件视图

此文为笔者近日有幸看到的一则关于计算机底层内存障碍的学术论文,并翻译(机译)而来[自认为翻译的还行],若读者想要英文原版的论文话,给我留言,我发给你。 内存障碍: 软件黑客的硬件视图...

Romane ⋅ 今天 ⋅ 0

SpringCloud 微服务 (七) 服务通信 Feign

壹 继续第(六)篇RestTemplate篇 做到现在,本机上已经有注册中心: eureka, 服务:client、order、product 继续在order中实现通信向product服务,使用Feign方式 下面记录学习和遇到的问题 贰 or...

___大侠 ⋅ 今天 ⋅ 0

gitee、github上issue标签方案

目录 [TOC] issue生命周期 st=>start: 开始e=>end: 结束op0=>operation: 新建issueop1=>operation: 评审issueop2=>operation: 任务负责人执行任务cond1=>condition: 是否通过?op3=>o......

lovewinner ⋅ 今天 ⋅ 0

浅谈mysql的索引设计原则以及常见索引的区别

索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索...

屌丝男神 ⋅ 今天 ⋅ 0

String,StringBuilder,StringBuffer三者的区别

这三个类之间的区别主要是在两个方面,即运行速度和线程安全这两方面。 首先说运行速度,或者说是, 1.执行速度 在这方面运行速度快慢为:StringBuilder(线程不安全,可变) > StringBuffer...

时刻在奔跑 ⋅ 今天 ⋅ 0

java以太坊开发 - web3j使用钱包进行转账

首先载入钱包,然后利用账户凭证操作受控交易Transfer进行转账: Web3j web3 = Web3j.build(new HttpService()); // defaults to http://localhost:8545/Credentials credentials = Wallet......

以太坊教程 ⋅ 今天 ⋅ 0

Oracle全文检索配置与实践

Oracle全文检索配置与实践

微小宝 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部