文档章节

Java算法--寻路

ChamPly
 ChamPly
发布于 2017/08/31 13:00
字数 1769
阅读 11
收藏 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
0
SpringFramework4系列之SpringTest:(二)MockJNDI

JNDI是J2EE 的标准之一,它依赖于容器, 比如说在开发测试阶段,datasource 或者jms 的factory 是通过JNDI所寻得的话,那么要测试的话,总是要部署到应用服务器上面 比如 TOmcat,weblogic或...

Garrry
2015/07/13
0
0
JVM系列第8讲:JVM 垃圾回收机制

在第 6 讲中我们说到 Java 虚拟机的内存结构,提到了这部分的规范其实是由《Java 虚拟机规范》指定的,每个 Java 虚拟机可能都有不同的实现。其实涉及到 Java 虚拟机的内存,就不得不谈到 Ja...

陈树义
11/21
0
0
Java项目开发

本人机械男,本科,转java项目开发。自学大半年,一看项目就晕菜。看项目书籍晕头转向,不知所云。奈何,寻解决之法。学习之法。望各位热心侠士不吝赐教,不胜感激。让我早日成为一名合格的j...

phoenix-yang
2015/08/05
2.1K
20
用大白话告诉你啥是Java开发

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

远方Java
06/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

十万个为什么之为什么大家都说dubbo

Dubbo是什么? 使用背景 dubbo为什么这么流行, 为什么大家都这么喜欢用dubbo; 通过了解分布式开发了解到, 为适应访问量暴增,业务拆分后, 子应用部署在多台服务器上,而多台服务器通过可以通过d...

尾生
19分钟前
1
0
Docker搭建代码质量检测平台-SonarQube(中文版)

Sonar是一个用于代码质量管理的开源平台,用于管理源代码的质量,可以从七个维度检测代码质量。通过插件形式,可以支持包括java,C#,C/C++,PL/SQL,Cobol,JavaScrip,Groovy等等二十几种编程语言...

Jacktanger
26分钟前
1
0
Windows / Linux / MacOS 设置代理上网的方法汇总

本文汇总了 Windows / Linux / MacOS 设置代理上网的各种方法,总结如下: 1、设置系统代理(Windows、Linux、MacOS) 2、设置代理插件(Chrome、Chromium、Firefox、Opera、QQ等浏览器) 3、...

sunboy2050
昨天
2
0
自定义 Maven 的 repositories

有时,应用中需要一些比较新的依赖,而这些依赖并没有正式发布,还是处于milestone或者是snapshot阶段,并不能从中央仓库或者镜像站上下载到。此时,就需要 自定义Maven的<repositories>。 ...

waylau
昨天
2
0
徒手写一个es6代码库

mkdir democd demonpm initnpm install -g babelnpm install -g babel-clinpm install --save-dev babel-preset-es2015-node5 在项目目录创建两个文件夹 functional-playground ......

lilugirl
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部