遡及法応用の迷宮問題

引き続き遡及法を応用して迷宮問題を解決する:問題は贅沢に述べて、一点から出口を見つければいい

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+="
";
    	}
    	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 QueeenIterator 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
    }
}

やっと書いたものが上がってきたので、私と同じ菜鳥に役に立つことを願っています.