寻找路径

package test;

import java.util.Scanner;

/**
 * 2017年4月23日
5
0 0 0 0 0 
1 1 1 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0
8
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
0 1 1 1 1 0 0 1
0 1 0 1 1 1 0 1
0 0 1 0 0 0 0 1
0 1 1 0 1 0 0 0
0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0


 */
public class Solution06 {
	static Chess[][] chessArray;
	static boolean [][] mapChess;
	static boolean logger;
	static boolean workout;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int test_case=2;
		for(int t=0;t<test_case;t++){
			chessArray=null;
			mapChess=null;
			workout=false;
			
			int size=sc.nextInt();
			int inputArray[][]=new int[size][size];
			mapChess=new boolean [size][size];
			for(int i=0;i<size;i++){
				for(int j=0;j<size;j++){
					inputArray[i][j]=sc.nextInt();
					
				}
			}
			
			chessArray=generateChessArray(inputArray);
			//System.out.println(chessArray[1][7].getChessStatus());
			process(chessArray[0][0],size);
		}
		
		sc.close();

	}
	
	

	private static void process(Chess chess,int size) {
		if(logger) System.out.println("遍历棋子："+chess.iIndex+","+chess.jIndex);
		if(chess.iIndex==size-1 && chess.jIndex==size-1){
			StringBuffer sb=new StringBuffer();
			
			while(true){
				//System.out.println("访问 "+chess.iIndex+","+chess.jIndex);
				sb.insert(0, (chess.iIndex+1)+","+(chess.jIndex+1)+" ");
				if(chess.iIndex==0 && chess.jIndex==0){
					break;
				}else{
					chess=chess.preChess;
				}
			}
			System.out.println(sb.toString());
			workout=true;
			
		}else{
			for(int i=0;i<chess.direct.length;i++){
				Chess c=null;
				if(logger) System.out.print("    方向："+i);
				if(chess.direct[i]==0  && chess.visited[i]==0 ){//有空白，没有访问过，可以访问 direct是方向，visited是否访问
					c=getNextChessBydirect(chess,i);
					if(! mapChess[c.iIndex][c.jIndex]){
						chess.visited[i]=1;
						c.preChess=chess;
						mapChess[chess.iIndex][chess.jIndex]=true;
						if(logger) System.out.println("可以访问，访问 "+c.iIndex+","+c.jIndex);
					}else{
						if(logger) System.out.println("不可以访问， "+c.iIndex+","+c.jIndex+" 以前访问过了");
						c=null;
					}
					
					
				}else{
					if(logger) System.out.println("不可以访问");
				}
				if((i==7) && (chess.direct[i]!=0 || chess.visited[i]==1) ){//到最后一个节点了
					//不是空白，或者已经访问过了,次节点不通
					mapChess[chess.iIndex][chess.jIndex]=false;
					
					c=chess.preChess;
					if(logger) System.out.println("所有节点都不可以访问了，需要退回到 "+c.iIndex+","+c.jIndex);
				}
				if(c!=null){
					process(c,size);
				}
				if(workout){
					break;
				}
			}
		}
			
		
	}



	/**
	 * 将二位数组生成二位对象数组
	 * @param inputArray
	 * @return
	 */
	private static Chess[][] generateChessArray(int[][] inputArray) {
		int size=inputArray.length;
		Chess[][] chessArray=new Chess[size][size];
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				Chess chess=new Chess();
				chess.iIndex=i;
				chess.jIndex=j;
				if(j==0){//最左边
					chess.direct[3]=-1;
					chess.direct[4]=-1;
					chess.direct[5]=-1;
				}else if(j== (size-1)){//到最右边了
					chess.direct[0]=-1;
					chess.direct[1]=-1;
					chess.direct[7]=-1;
				}
				if(i==0){//最上面
					chess.direct[5]=-1;
					chess.direct[6]=-1;
					chess.direct[7]=-1;
				}else if(i==(size-1)){//最下面
					chess.direct[1]=-1;
					chess.direct[2]=-1;
					chess.direct[3]=-1;
				}
				
				{
					if(chess.direct[0]!=-1 && inputArray[i][j+1]==1){//右侧有棋子
						chess.direct[0]=1;
					}
					if(chess.direct[1]!=-1 && inputArray[i+1][j+1]==1){//右下侧有棋子
						chess.direct[1]=1;
					}
					if(chess.direct[2]!=-1 && inputArray[i+1][j]==1){//下侧有棋子
						chess.direct[2]=1;
					}
					if(chess.direct[3]!=-1 && inputArray[i+1][j-1]==1){//左下侧有棋子
						chess.direct[3]=1;
					}
					if(chess.direct[4]!=-1 && inputArray[i][j-1]==1){//左侧有棋子
						chess.direct[4]=1;
					}
					if(chess.direct[5]!=-1 && inputArray[i-1][j-1]==1){//左上侧有棋子
						chess.direct[5]=1;
					}
					if(chess.direct[6]!=-1 && inputArray[i-1][j]==1){//上侧有棋子
						chess.direct[6]=1;
					}
					if(chess.direct[7]!=-1 && inputArray[i-1][j+1]==1){//右上侧有棋子
						chess.direct[7]=1;
					}
					
				}
				
				chessArray[i][j]=chess;
			}
		}
		
		return chessArray;
	}
	
	public static Chess getNextChessBydirect(Chess chess,int d){//右边0，  右下1，下2，左下3，  左4，  左上5，上6，右上7    空白存储0，有子存储1，边界外存储-1
		
		if(d==0){
			return chessArray[chess.iIndex][chess.jIndex+1];
		}else if(d==1){
			return chessArray[chess.iIndex+1][chess.jIndex+1];
		}
		else if(d==2){
			return chessArray[chess.iIndex+1][chess.jIndex];
		}
		else if(d==3){
			return chessArray[chess.iIndex+1][chess.jIndex-1];
		}
		else if(d==4){
			return chessArray[chess.iIndex][chess.jIndex-1];
		}
		else if(d==5){
			return chessArray[chess.iIndex-1][chess.jIndex-1];
		}
		else if(d==6){
			return chessArray[chess.iIndex-1][chess.jIndex];
		}
		else if(d==7){
			return chessArray[chess.iIndex-1][chess.jIndex+1];
		}else{
			return null;
		}
	}

	
	

}
class Chess{
	int iIndex;
	int jIndex;
	int direct[] =new int[8];//右边0，  右下1，下2，左下3，  左4，  左上5，上6，右上7    空白存储0，有子存储1，边界外存储-1
	int visited[]=new int[8];//没有访问过是 0，访问过但没有通过是 1
	
	public Chess preChess;//前一个节点
	public Chess linkChess;//当前要访问的节点
	
	
	
	public String getChessStatus(){
		
		StringBuffer sb=new StringBuffer();
		
		if(direct[0]==1) {//右侧有棋子
			sb.append("右侧有棋子 ");
		}
		if(direct[1]==1 ){//右下侧有棋子
			sb.append("右下侧有棋子 ");
		}
		if(direct[2]==1 ){//下侧有棋子
			sb.append("下侧有棋子 ");
		}
		if(direct[3]==1 ){//左下侧有棋子
			sb.append("左下侧有棋子 ");
		}
		if(direct[4]==1 ){//左侧有棋子
			sb.append("左侧有棋子 ");
		}
		if(direct[5]==1 ){//左上侧有棋子
			sb.append("左上侧有棋子 ");
		}
		if(direct[6]==1 ){//上侧有棋子
			sb.append("上侧有棋子 ");
		}
		if(direct[7]==1 ){//右上侧有棋子
			sb.append("右上侧有棋子 ");
		}
		
		if(direct[0]==0) {//右侧有空白
			sb.append("右侧有空白 ");
		}
		if(direct[1]==0 ){//右下侧有空白
			sb.append("右下侧有空白 ");
		}
		if(direct[2]==0 ){//下侧有空白
			sb.append("下侧有空白 ");
		}
		if(direct[3]==0 ){//左下侧有空白
			sb.append("左下侧有空白 ");
		}
		if(direct[4]==0 ){//左侧有空白
			sb.append("左侧有空白 ");
		}
		if(direct[5]==0 ){//左上侧有棋子
			sb.append("左上侧有空白 ");
		}
		if(direct[6]==0 ){//上侧有空白
			sb.append("上侧有空白 ");
		}
		if(direct[7]==0 ){//右上侧有棋子
			sb.append("右上侧有空白 ");
		}
		return sb.toString();
	}
	
	
}