aknightsjourney.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;


/**
 * ID:2488
 * DFS
 * @author yhm
 *
 */
public class AKnightsJourney {
	static int R,C;
	static boolean [][] board;
	static boolean Find;
	static String resultPath;

	static final int[][] move = { { -1, -2 }, { 1, -2 }, { -2, -1 }, { 2, -1 },
		{ -2, 1 }, { 2, 1 }, { -1, 2 }, { 1, 2 }};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			R = cin.nextInt();
			C = cin.nextInt();
			board = new boolean[R][C];
			Find = false;
			DFS(0,0,1,"");
			System.out.println("Scenario #"+(i+1)+":");
			if(Find){
				System.out.println(resultPath);
			}
			else{
				System.out.println("impossible");
			}
			System.out.println();
		}

	}
	
	static boolean overflow(int row, int col){
		return (row<0 || col<0 || row>=R || col>=C);
	}
	
	static void DFS(int row, int col, int step, String path){
		path+=translate(row, col);
		board[row][col] = true;
		if(step==R*C){
			resultPath = path;
			Find = true;
			return;
		}
		for(int i=0;i<8 && !Find;i++){
			int newR = row+move[i][0];
			int newC = col+move[i][1];
			if(!overflow(newR,newC)){
				if(!board[newR][newC]){
					DFS(newR,newC,step+1,path);
				}				
			}
		}
		board[row][col] = false;
		
	}

	static String translate(int row, int col){
		char ch = (char)(col+'A');
		int ch1 = row+1;
		String str = "";
		str+= ch;
		str+= ch1;
		return str;
	}
}