package cn.lys.thoughtwork;
import java.util.ArrayList;
import java.util.List;
public class GraphMap {
private static final char START_NODE = 'A';
public static final String NO_SUCH_ROUTE = "NO SUCH ROUTE";
public static final int OPTIMAL_ALGORITHM = -1;
public static final int UNLIMITED_STOPS = Integer.MAX_VALUE;
public static final int UNLIMITED_DISTANCE = -1;
private static List<Route> routes;
/**
* Map of ABCDE places.
* Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 .
**/
private int[][] map = {
/** A B C D E **/
/** A **/{0, 5, 0, 5, 7},
/** B **/{0, 0, 4, 0, 0},
/** C **/{0, 0, 0, 8, 2},
/** D **/{0, 0, 8, 0, 6},
/** E **/{0, 3, 0, 0, 0}
};
public static void main(String[] args) {
GraphMap gm = new GraphMap();
char start = 'B';
char end = 'B';
int stops = -4;
int maxDistance = -1;
gm.makeTripFromStart2End(start, end, stops, maxDistance);
}
/**
* Get the distance of the route which you input.
* @param start: Position of starting.
* @param end: Position of ending.
* @return The distance between 'start' and 'end'.
*/
public int getDistance(char start, char end){
return getLengthByIndex(start - START_NODE, end - START_NODE);
}
/**
* Find all routes from 'start' to 'end'.
* @param start: The starting of route.
* @param end: The ending of route.
* @param stops: The max stops in this route.
* @param maxDistance: The max distance in this route.
* @return The trip contains all routes from 'start' to 'end'.
*/
public Trip makeTripFromStart2End(char start, char end, int stops, int maxDistance){
if (!checkPosition(start - START_NODE, end - START_NODE)) {
return null;
}
// init routes param
routes = new ArrayList<Route>();
// find all routes
search(start - START_NODE, end - START_NODE, "" + start, 0, stops, maxDistance);
// construct a trip that contains all routes
Trip trip = new Trip(routes, start, end);
return trip;
}
/**
* find all routes that meet the requirements.
* @param x
* @param y
*/
private void search(int x, int y, String path, int distance, int stops, int maxDistance){
for(int i=0;i<map[x].length;i++){
// 1.exist a route;
// 2.stops < requirement stops;
// 3.eliminate the starting;
// 4.don't walk repeated station.
// 5.distance < maxDistance
if(map[x][i] > 0 && (stops > 0 ? (path.length() < stops + 1) : (!path.substring(1).contains(String.valueOf((char)(i + START_NODE)))))
&& (maxDistance > 0 ? (distance < maxDistance - map[x][i]) : true)){
// arrive the ending
if(i == y){
routes.add(new Route(path + (char)(y + START_NODE), distance + map[x][i]));
System.out.println("path=" + path + (char)(y + START_NODE) + ", distance=" + (distance + map[x][i]));
}
search(i, y, path + (char)(i + START_NODE), distance + map[x][i], stops, maxDistance);
}
}
}
/**
* Get the distance by index in this map.
* @param x: X-axis in this map.
* @param y: Y-axis in this map.
* @return 0 represents illegal params or there doesn't exist the route between x and y.
*/
private int getLengthByIndex(int x, int y){
if (!checkPosition(x, y)) {
return 0;
}
return map[x][y];
}
/**
* x,y params must be legal in this situation
* @param x
* @param y
* @return
*/
private boolean checkPosition(int x, int y){
if (x < 0 || y < 0 || x > map.length || y >= map.length) {
return false;
}
return true;
}
public int[][] getMap() {
return map;
}
public void setMap(int[][] map) {
this.map = map;
}
}
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
ThoughtWorksInterview.zip (15个子文件)
ThoughtWorksInterview
bin
cn
lys
thoughtwork
Trains.class 2KB
Route.class 755B
test
TrainsTest.class 2KB
GraphMap.class 3KB
Main.class 1KB
Trip.class 3KB
.settings
org.eclipse.jdt.core.prefs 598B
src
cn
lys
thoughtwork
GraphMap.java 4KB
test
TrainsTest.java 3KB
Trains.java 2KB
Trip.java 1KB
Route.java 532B
Main.java 268B
.project 397B
.classpath 379B
共 15 条
- 1
资源评论
- weixin_445611712019-02-24very good!!!
- mkasoy2019-08-22感谢,参考了一下
- baichilvle2019-09-01有种被忽悠的感觉
ls0111
- 粉丝: 55
- 资源: 25
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- CVE-2019-0708漏洞检测与利用工具
- STM32单片机FPGA毕设电路原理论文报告利用c8051f020系列单片机实现智能仪器开发
- STM32单片机FPGA毕设电路原理论文报告利用8位单片机实现与Internet网络通信应用研究
- STM32单片机FPGA毕设电路原理论文报告利用80C196单片机测量三相异步电动机功率因数
- STM32单片机FPGA毕设电路原理论文报告力学传感器与单片机的接口设计
- p107-u07FLT2.wav
- STM32单片机FPGA毕设电路原理论文报告雷达幅频特性测试仪的智能化研究
- STM32单片机FPGA毕设电路原理论文报告可组网电子温湿度测量仪的设计与实现
- STM32单片机FPGA毕设电路原理论文报告可在单片机上实现的语音混沌保密通信方法
- STM32单片机FPGA毕设电路原理论文报告可实现的基于MCS51单片机的恒温控制系统的设计
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功