回溯法应用之迷宫问题

继续应用回溯法解决迷宫问题：
问题赘述一下，从一点出发找到出口即可

package 数据结构及算法.回溯法应用之迷宫问题;

import java.util.Iterator;

import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.Position;

public class Maze implements Application{
    private static final byte WALL=0;
    private static final byte CORRIDOR=1;//非墙，走廊
	private static final byte PATH=9;
	private static final byte TRIED=2;
	
	private Position finish;
	
	private byte[][] grid;
	
	public Maze(byte[][]grid,Position finish){
		this.finish=finish;
		this.grid=grid;
	}
	
	@Override
	public boolean valid(Position pos) {
		if(pos.getRow()>=0&&
				pos.getRow()<this.grid.length&&
				pos.getColumn()>=0&&
				pos.getColumn()<this.grid[0].length&&
				grid[pos.getRow()][pos.getColumn()]==this.CORRIDOR){
			return true;
		}
		return false;
	}

	@Override
	public void record(Position pos) {
		grid[pos.getRow()][pos.getColumn()]=this.PATH;	
	}

	@Override
	public boolean done(Position pos) {
		return this.finish.getRow()==pos.getRow()&&this.finish.getColumn()==pos.getColumn();
	}

	@Override
	public void undo(Position pos) {
		this.grid[pos.getRow()][pos.getColumn()]=this.TRIED;
	}

	public String toString(){
    	String result="";
    	for(int i=0;i<this.grid.length;i++){
    		for(int j=0;j<this.grid[0].length;j++){
    			result+=this.grid[i][j]+" ";
    		}
    		result+="\n";
    	}
    	return result;
    }
	
	@SuppressWarnings("rawtypes")
	@Override
	public Iterator  iterator(Position pos) {
		return new MazeIterator(pos);
	}
	
	@SuppressWarnings("rawtypes")
	private class MazeIterator implements Iterator{
        private int row=0;
        private int column=0;
        private int count=0;
		public MazeIterator(Position pos) {
			this.row=pos.getRow();
			this.column=pos.getColumn();
		}

		@Override
		public boolean hasNext() {
			return this.count<4;
		}

		@Override
		public Object next() {
			Position nextPosition=new Position();
			switch(count){
			case 0:nextPosition=new Position(row-1,column);
			
			   break;//north
			case 1:nextPosition=new Position(row,column+1);
		       break;//east
			case 2:nextPosition=new Position(row+1,column);
		       break;//south
			case 3:nextPosition=new Position(row,column-1);
		       break;//west
			}
			count++;
			return nextPosition;
		}

		@Override
		public void remove() {
		    throw new UnsupportedOperationException();	
		}
		
	}
	    	 
}

初始情况是输入的整个矩阵，1表示可走的，0表示墙
public boolean valid(Position pos)中判断为在矩阵内切非墙有效
在public void record(Position pos)中我让该位置记为9.表示走过
public void undo(Position pos)，撤销时与上是逆过程；记为2，

private class QueenIterator implements Iterator为内部类，记录某位置的下一行可选位置，按照北，东，南，西的顺序找


测试程序如下

package 数据结构及算法.回溯法应用之迷宫问题;

import java.util.Scanner;

import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.BackTrack;
import 数据结构及算法.回溯法.Position;

public class MazeTest {
    
    private byte[][]grid;
    public MazeTest(byte[][]grid){
    	Scanner sc=new Scanner(System.in);
    	String prompt="请输入四个数字，分别作为迷宫的起始点与终点的row,column坐标！";
    	System.out.println(prompt);
    	String s=sc.nextLine();
    	this.grid=grid;
    	pocessInput(s);
    }
	
	public void pocessInput(String s) {
		String[] ss=s.split(" ");
		int startR=Integer.parseInt(ss[0]);
		int startC=Integer.parseInt(ss[1]);
		int finalR=Integer.parseInt(ss[2]);
		int finalC=Integer.parseInt(ss[3]);
		
		Position startPosition=new Position(startR,startC);
		Position finalPosition=new Position(finalR,finalC);
		
		Application app=new Maze(grid, finalPosition);
		BackTrack backTrack=new BackTrack(app);
		
		
		println("开始为：");
		println(app.toString());
		if(!app.valid(startPosition)||!app.valid(finalPosition)){
			println("failure!");
		}
		else{
			app.record(startPosition);
			if(app.done(startPosition)||backTrack.tryToSolve(startPosition)){
				println("success");
			}
			else{
				app.undo(startPosition);
				println("failure!");
			}
		}
		println("最终为：");
		println(app.toString());
		
	}
	public void println(String s){
		System.out.println(s);
	}
    public static void main(String[]args){
    byte[][] grid={{1,1,1,0,1,1,0,0,0,1,1,1,1},
			       {1,0,1,1,1,1,0,1,1,1,1,1,0},
			       {1,0,0,0,1,0,1,0,1,0,1,0,1},
			       {1,0,0,0,1,1,1,0,1,0,1,1,1},
			       {1,1,1,1,1,0,0,0,0,1,0,0,0},
			       {0,0,0,0,1,0,0,0,0,0,0,0,0},
			       {0,0,0,0,1,1,1,1,1,1,1,1,1}
			      };
    	new MazeTest(grid);//测试用例 0 0 6 12
    }
}

终于把写的东西弄上来了，希望对和我一样的菜鸟有帮助