그림 의 깊이 우선 검색 - 미로 풀이 공간

1. 원리 설명:
  주어진 그림 G 의 초기 상 태 는 모든 정점 에 접근 한 적 이 없 으 며, G 에서 정점 V 를 초기 출발점 (원점, 루트 노드) 으로 선택 하 십시오.
다음 과 같이 설명 합 니 다. 먼저 출발점 V 에 접근 하고 방문 한 것 으로 표시 합 니 다.그리고 차례대로 V 에서 출발 하여 V 의 각 인접 점 (자 결점) W 를 검색 합 니 다.
W 가 접근 하지 않 았 다 면, W 를 새로운 출발점 으로 깊이 우선 순 위 를 계속 옮 겨 다 니 며, 그림 의 모든 원점 V 와 경로 가 같은 정점 (원점 에서
도달 할 수 있 는 정점) 이 모두 방문 되 었 을 때 까지.이 그림 에 접근 하지 않 은 정점 이 있다 면, 접근 하지 않 은 정점 을 새로운 원점 으로 선택 하여 반복 합 니 다.
이 과정 은 그림 의 모든 정점 이 방문 되 었 을 때 까지 입 니 다.
2. 알고리즘 설명
  (1) 그림 의 저장 방식 을 확인한다.
  (2) 디자인 검색 과정 에서 의 작업 은 출력 문 제 를 해결 하기 위 한 저장 작업 을 포함한다.
  (3) 문제 의 해 를 검색 하면 출력 합 니 다.그렇지 않 으 면 돌 이 켜 보면
  (4) 일반적으로 거 슬러 올 라 가기 전에 결점 을 원시 상태 로 회복 해 야 한다. 특히 문 제 를 많이 푸 는 과정 에서.
3. 일종 의 실현: 미로 문제.입 구 를 정 하고 출구 의 해 공간 을 찾 습 니 다.

package com.maozj.datastruct.graphic;

/**
 * create on 2010.05.15   ：        
 * 
 * @author    
 * @version v1.0
 * 
 * 
 */
public class DeepSearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		DeepSearch ds = new DeepSearch();
		ds.search(0, 0);
		System.out.println("
"+ds.getTotal());
	}

	private int[][] maze = {
			{ 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 1, 1, 1, 1, 0, 1, 0 }, 
			{ 0, 0, 0, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 0, 0, 0, 1, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 1, 0 },
			{ 0, 1, 0, 0, 0, 0, 1, 1 }, 
			{ 0, 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 1, 1, 1, 1, 0 } };
	
	private int[] fx = { 1, -1, 0, 0 };
	private int[] fy = { 0, 0, -1, 1 };
	private int total;

	public DeepSearch() {
		total = 0;
		//           
		maze[0][0] = 3;
	}

	public void search(int i, int j) {
		int k, newi, newj;
		//        
		for (k = 0; k < 4; k++)
			if (check(i, j, k)) {
				newi = i + fx[k];
				newj = j + fy[k];
				//       ，       
				maze[newi][newj] = 3;
				//        ，       
				if (newi == 7 && newj == 7) {
					Out();
				} else {
					search(newi, newj);
				}
			}
		//           
		maze[i][j] = 2;
	}

	public void Out() {
		int i, j;
		for (i = 0; i < 8; i++) {
			System.out.println("");
			for (j = 0; j < 8; j++) {
				if (maze[i][j] == 3) {
					System.out.print("V");
					total++;
				} else {
					System.out.print("*");
				}
			}
		}
	}

	public boolean check(int i, int j, int k) {
		boolean bool = true;
		i += fx[k];
		j += fy[k];
		if (i < 0 || i > 7 || j < 0 || j > 7) {//       
			bool = false;
		} else if (maze[i][j] != 0) {//     
			bool = false;
		}
		return bool;
	}

	public int getTotal() {
		return total;
	}

}