POJ 3984 迷宮問題 (DFS(深度優先搜索))

迷宮問題
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6322   Accepted: 3673

Description

定義一個二維數組：

int maze[5][5] = {

 0, 1, 0, 0, 0,

 0, 1, 0, 1, 0,

 0, 0, 0, 0, 0,

 0, 1, 1, 1, 0,

 0, 0, 0, 1, 0,

};
它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。
Input

一個5 × 5的二維數組，表示一個迷宮。數據保證有唯一解。
Output

左上角到右下角的最短路徑，格式如樣例所示。
Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路： DFS算法

import java.io.*;
import java.util.*;

public class Main {
	public static int map[][] = new int[5][5];
	public static int fx[] = { 0, 0, 1, -1 };
	public static int fy[] = { 1, -1, 0, 0 };
	public static int px, py;
	public static void main(String[] args) {
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		while (sc.hasNextInt()) {
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[i].length; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			map[0][0] = 3;//標記走過
			px = 0;
			py = 0;
			DFS(0, 0);	
		}
	}

	public static void DFS(int p1, int p2) {
		if (p1 == map.length - 1 && p2 == map[0].length - 1){
			out();
			return;
		}
		else {
			//四個方向進行判定
			for (int i = 0; i < 4; i++) {
					int px = p1 + fx[i];
					int py = p2 + fy[i];
					if (check(px, py)) {
						map[px][py] = 3;//標記走過的路
						DFS(px, py);
				}
			}
		}
	}
	public static void out() {
		for (int i = 0; i <5; i++) {
			for (int j = 0; j <5; j++) {
				if (map[i][j] == 3) {
					System.out.println("(" + i + ", " + j + ")");
				}
			}
		}
	}

	public static boolean check(int p1, int p2) {

		if (p1 < 0 || p1 > map[0].length - 1 || p2 < 0 || p2 > map.length - 1
				|| map[p1][p2] != 0)
			return false;
		else
			return true;
	}
}