文档章节

Java算法--寻路

ChamPly
 ChamPly
发布于 2017/08/31 13:00
字数 1769
阅读 10
收藏 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
Java实习总结网易百度小米美团阿里(均offer)

本人是大三的软件工程专业学生,从2017年3月开始学Java,从那时候还不知道什么是接口,到现在分布式也有所了解,很幸运的拿到了这些offer 2017年10月 网易考拉 Java 12月 百度 Java 2018年 ...

牛客网
06/22
0
0
《成神之路-基础篇》JVM——垃圾回收(已完结)

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

05/05
0
0
My java——JVM(垃圾回收)四

续My java——JVM(内存域) 中讲述了Java在JVM中的内存使用,其实在我们出来java程序时基本上有两个地方的内存处理 一是栈、二是堆,JVM会自动回收堆中的内存,也就我们所说的垃圾回收,那J...

tngou
2013/03/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

74.expect脚本同步文件以及指定host同步文件 构建分发系统文件和命令

20.31 expect脚本同步文件: 在expect脚本中去实现在一台机器上把文件同步到另外一台机器上去。核心命令用的是rsync ~1.自动同步文件 #!/usr/bin/expect set passwd "123456" spawn rsync -a...

王鑫linux
32分钟前
0
0
TypeScript项目引用(project references)

转发 TypeScript项目引用(project references) TypeScript新特性之项目引用(project references) 项目引用是TypeScript 3.0中的一项新功能,允许您将TypeScript程序构建为更小的部分。 通过这...

durban
37分钟前
0
0
爬虫入门

导读 网络爬虫(Web crawler),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本,它们被广泛用于互联网搜索引擎或其他类似网站,可以自动采集所有其能够访问到的页面内容,以获取...

问题终结者
37分钟前
0
0
ppwjs之bootstrap文字排版:无序列表项不换行

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
44分钟前
0
0
SpringBoot 学习一

本文将从以下几个方面介绍: 前言 HelloWorld 读取配置文件 例子(CURD) 前言 Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架...

tsmyk0715
44分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部