package com.java.study;
import java.util.*;
/*
* 假设有机器人坐在X*Y网格左上角，机器人要从(0,0)走到(X,Y)，
* 假设有些点为禁区，机器 人不能踏足，设计一种算法，找出一条路径，让机器人从左上角移动到右下解。
* 例：
0000000000
0000000000
0010101011
1101001000
其中1为禁区
*/
public class MysteryGong {
public static class PathPoint{
public int x; //第x行
public int y; //第y列
public int direct; //方向 0表示向下，1表示向右
public int counter;//该位置经过的次数
public PathPoint(int x,int y,int direct,int counter){
this.x=x;this.y=y;this.direct=direct;this.counter=counter;
}
}
public static void main(String[] args) {
int array[][]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,1,0,1,0,1,1},
{1,1,0,1,0,0,1,0,0,0}
};//风格以二维数组形式存储
findPath1(array);
findPath2(array);
}//采用回溯的方法
public static void findPath1(int[][] array){
int m=array.length; //总行数
int n=array[0].length;//总列数
int right=1;
int down=0;
Deque<PathPoint> stack=new LinkedList<PathPoint>();
stack.push(new PathPoint(0,0,0,0));
boolean status=false;
while(!stack.isEmpty()){
PathPoint point=stack.pop(); //pop出来一次，表示访问一次
if(point.x==m-1 && point.y==n-1){
status=true; //走到右下角时，找到路径
stack.push(point);//维护路径完整性
break;
}else{
if(array[point.x][point.y]!=1){ //该点不是阻塞点
if(point.counter!=2){ //当回溯到该点时，若counter==2,表示该点已走过两次，即向右向下都试过了，删除该点
if(!(point.x==m-1 || point.y==n-1)){
stack.push(new PathPoint(point.x,point.y,point.direct+1,point.counter+1));//该点位置访问次数加1，方向标号+1
if(point.direct==0){ //表示当前要向下走，
stack.push(new PathPoint(point.x+1,point.y,0,0));
}else{ //表示当前要向右走
stack.push(new PathPoint(point.x,point.y+1,0,0));
}
}
//处理最后一行
if(point.x==m-1){ //最后一行，只能向右走
stack.push(new PathPoint(point.x,point.y+1,right,0));
}
//处理最后一列的情况
if(point.y==n-1){ //到达最后一列，只能向下走
stack.push(new PathPoint(point.x+1,point.y,down,0));
}
}
}
}
}
if(status==false){
System.out.println("不存在满足条件的路径");
}else{
//输出栈中路径
System.out.println("找到一条满足条件的路径 ：");
printPath(stack);
}
}
public static void printPath(Deque<PathPoint> stack){
if(stack.isEmpty()) return;
PathPoint point=stack.pop();
printPath(stack);
System.out.print("("+point.x+","+point.y+")");
}
/*
一般递归方法 ：从终点往回走，从最后一点开始，试着找出一条到其相邻点的路径
*/
public static void getPath1(int x,int y,ArrayList<Point> path){
Point p=new Point(x,y);
path.add(p);
if(x==0 &&y ==0) return true;
bolean success=false;
if(x>=1 && isFree(x-1,y)){ //试着向左走
success=getPath1(x-1,y,path);
}
if(!success && y>=1 && isFree(x,y-1)){
success=getPath(x,y-1,path);
}
if(!success)
path.add(p); //错了，最好不要走这里。
return success;
}
/*采用动态规划方法 ： 一般递归方法 +缓存结果
使用缓存记录已走过的点。以防再次走
效果同回溯相同，只是实现时更加简单
*/
public static void findPath3(int x,int y,ArrayList<Point> path,Hasthtable<Point,boolean> cache){
Point p=new Point(x,y);
if(cache.contains(key)) { //已访问过这个点
return cache.get(p);
}
path.add(p);
if(x==0 &&y ==0) return true; //找到一条路径
if(x>=1 && isFree(x-1,y)){ //试着向左走
success=getPath1(x-1,y,path,cache);
}
if(!success && y>=1 && isFree(x,y-1)){
success=getPath(x,y-1,path,cache);
}
if(!success)
path.add(p); //错了，最好不要走这里。
cache.put(p,succcess);
return success;
}
}
}
评： 采用一般递归方法 ： 类似于穷举法 实现简单
采用回溯：用栈来实现，可以保存之前的结果 迭代方式 实现复杂
采用动态规划：一般递归法+缓存结果 效果等同于回溯 实现简单