Amazon OA2准备——迷宫

Find Path in 2D matrix

输入一个2D的int array，其中有0，1，9。

0为墙壁 1为可以通过，9 为需要找的结果，这道题如果真是1是路，找9比较好，可以直接用大于符号。一亩三分地里面也有人说0是可以通过，1是墙壁，只能看着来了。出生点我定为（0,0）因为我不确定OA中给的是不是（0,0）

返回true or false，表示可以找到9或者没有办法找到。9不一定只有一个。

需要注意的特殊情况是第一个就是需要找的9，eg. { {9}}

想了一下，应该是上下左右都可以活动才对，所以又加了两个方向。感觉可以把Korsh原来写的炫酷的迷宫游戏写出来了。还是做面试准备先。

先给出我自己用来测试的一些例子

		int[][] maze = {
   {1,0,0,0,0},{1,1,1,1,1},{1,0,0,0,0},{0,0,9,0,0}};int[][] maze = {
   {1,0,0,0,0},{1,1,1,1,1},{1,0,0,0,1},{0,0,9,1,1}};		int[][] maze = {
   {1,1,1,1},{1,0,0,0},{1,9,0,0}};int[][] maze = {
   {9}};int[][] maze ={
   {1,1,1,1,1,1},{1,1,1,1,0,0},{0,0,1,0,0,0},{1,1,1,1,1,1},{1,0,0,0,1,0},{1,1,1,0,9,0}};

我觉得这道题用BFS比较清晰一点。虽然后来自己也改乱了。不过脑子清晰一点。

	private static boolean bfs(int[][] maze, int startx, int starty) {// TODO Auto-generated method stubif(maze == null)return false;if(maze.length < 1 || maze[0].length < 1)return false;LinkedList<Point> que = new LinkedList<Point>();Point p1 = new Point(startx,starty, maze[startx][starty]);que.offer(p1);int width = maze[0].length;int height = maze.length;p1 = que.poll();while(p1.val != 9){int x = p1.x;int y = p1.y;maze[x][y] = -1;if((x+1) < height){if(maze[x+1][y] > 0){Point p2 = new Point(x+1,y, maze[x+1][y]);que.offer(p2);}}if((x-1) >= 0){if(maze[x-1][y] > 0){Point p2 = new Point(x-1,y, maze[x-1][y]);que.offer(p2);}}if((y+1) < width)if(maze[x][(y+1)] > 0){Point p2 = new Point(x,(y+1), maze[x][(y+1)]);que.offer(p2);}if((y-1) >= 0)if(maze[x][(y-1)] > 0){Point p2 = new Point(x,(y-1), maze[x][(y-1)]);que.offer(p2);}if(que.isEmpty()){break;}elsep1 = que.poll();}if(p1.val ==9)return true;elsereturn false;}

	private static boolean dfs(int[][] maze, int start_x, int start_y) {// TODO Auto-generated method stubif(maze == null)return false;if(maze.length < 1 ||maze[0].length <1)return false;Stack<Point> stack = new Stack<Point>();int width = maze[0].length;int height = maze.length;Point p = new Point(start_x,start_y, maze[start_x][start_y]);stack.push(p);while(p.val != 9){boolean flag = false;int x = p.x;int y = p.y;maze[p.y][p.x] = -1;if((x+1) < width && maze[y][x+1] > 0){flag = true;x=x+1;p = new Point(x,y, maze[y][x]);stack.push(p);}else if((x-1)> 0 && maze[y][x-1] >0){flag = true;x=x-1;p = new Point(x,y, maze[y][x]);stack.push(p);}else if((y-1)> 0 && maze[y-1][x] >0){flag = true;y=y-1;p = new Point(x,y, maze[y][x]);stack.push(p);}else if((y+1) < height && maze[y+1][x] >0){flag = true;y=y+1;p = new Point(x,y, maze[y][x]);stack.push(p);}if(stack.isEmpty()){return false;}	if(!stack.isEmpty() && flag == false){p = stack.pop();}}if(p.val == 9)return true;elsereturn false;}