寒假17：迷宫问题01，能否走出去

昨天晚上老师讲了下迷宫问题，感觉听懂了。然后自己算是拓展下，加了一道墙，省掉后面一大部分的判断，然后将四个方向合并到一个for循环里面了。

 

 

迷宫问题

Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 18565 Accepted: 10989

 

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 0

Sample Output

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

Source

 

代码部分：

 

 

import java.util.Scanner; public class migong { static int[][] map=new int[7][7]; static int[][] visited=new int[7][7]; static boolean flag=false; //四个方向，放在一个数组里 static int[][] fx=new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); for (int i = 0; i < 7; i++) { for (int j = 0; j < 7; j++) { if(i==0||j==0||i==6||j==6)//加一道墙 map[i][j]=1; else{ map[i][j]=sc.nextInt(); } } } dfs(1,1); if(flag) System.out.println("OK!"); else System.out.println("NO!"); } private static void dfs(int i, int j) { //到达终点 if(i==5&&j==5){ flag=true; return; } for (int k = 0; k < 4; k++) { if(check(i+fx[k][0],j+fx[k][1])){ visited[i+fx[k][0]][j+fx[k][1]]=1; dfs(i+fx[k][0],j+fx[k][1]); } } // //向下走 // if(check(i,j+1)){ // visited[i][j+1]=1; // dfs(i,j+1); // } // //向右走 // if(check(i+1,j)){ // visited[i+1][j]=1; // dfs(i+1,j); // } // //向上走 // if(check(i,j-1)){ // visited[i][j-1]=1; // dfs(i,j-1); // } // //向左走 // if(check(i-1,j)){ // visited[i-1][j]=1; // dfs(i-1,j); // } } //检查是否可以走 private static boolean check(int i, int j) { if(map[i][j]!=1&&visited[i][j]!=1) return true; else{ return false; } } }