【面试】如何找到迷宫出口-白红宇

【面试】如何找到迷宫出口

阅读量：6283 次

发布时间：2019-06-22

本文共 7954 字，大约阅读时间需要 26 分钟。

一、问题描述

给出如下的矩阵

1 1 1 1

0 0 0 1

1 9 0 0

1 1 1 1

其中1代表此位置是可以通过的，0代表此位置是不可通过的，要从起点开始，确定是否存在这样一条路径，可以从起点找到数字9。也就是找到这样一条路径1->1->1 ...... ->9。这个问题是寻找迷宫出口的变形。可以将9看成是迷宫的出口，而给出的开始位置是迷宫的入口，寻找一条路径。

二、问题求解

当矩阵阶数不是太大的时，可以使用递归来求解，但是，当矩阵的阶数变得很大时，则需要使用另外的方法进行计算，也就是采用栈来进行求解。

下面是两种解决方法

1.当矩阵阶数较小时，采用递归进行求解，这种方式只是用来开拓思路，解此问题存在一定的局限性。

源代码如下：

import java.util.Scanner;public class MatrixPath {	public static void main(String[] args) {		Scanner scan = new Scanner(System.in);		String line = scan.nextLine();	//输入行和列		String[] lines = line.split("\\s+");//分离行和列		int row = Integer.parseInt(lines[0]);		int col = Integer.parseInt(lines[1]);				int[][] matrix = new int[row + 2][col + 2];	//将外层包围一层0元素		footPrints = new boolean[row + 2][col + 2];		endPrints = new boolean[row + 2][col + 2];  				for(int i = 0; i < row; i++) {	//初始化数组元素			line = scan.nextLine();			lines = line.split("\\s");			for(int j = 0; j < lines.length; j++) {				matrix[i + 1][j + 1] = Integer.parseInt(lines[j]);			}		}				scan.close();				int startX = 1;	//入口横坐标		int startY = 1;	//入口纵坐标				System.out.println(exsitPath(startX, startY, row, col, matrix) + " ");	}		public static boolean exsitPath(int x, int y, int row, int col, int[][] matrix) {		if(x < 0 || y < 0 || x >= row || y >= col)			return false;		if(matrix[x][y] == 9)			return true;		if(matrix[x][y] == 0)			return false;		if(exsitPath(x + 1, y, row, col, matrix) || exsitPath(y - 1, x, row, col, matrix) || exsitPath(x, y - 1, row, col, matrix) || exsitPath(x, y + 1, row, col, matrix))			return true;		return false;	}}

测试用例：

3 3

1 1 1

1 9 1

0 1 1

输出结果为：true

测试用例：

4 4

1 1 1 1

0 0 0 1

0 0 1 1

9 1 1 1

输出结果：java.lang.StackOverflowError，堆栈溢出

2.使用递归的方法要选择好测试用例，很可能因为测试用例的选取不恰当而造成堆栈溢出。递归只是为了开拓思路而已，下面使用栈结构来解决堆栈溢出的问题。

源代码如下：

package com.leesf.Main;import java.util.ArrayList;import java.util.Scanner;class Position {//位置信息    private int x;    private int y;        public Position(int x, int y) {        this.x = x;        this.y = y;    }        public int getX() {        return x;    }        public int getY() {        return y;    }}class Item {//栈中元素类型    private int order;    //第几步    private Position seat;    //位置    private int value;    //对应的值    private int di;    //方位        public Item(int order, Position seat, int value, int di) {        this.order = order;        this.seat = seat;        this.value = value;        this.di = di;    }        public int getOrder() {        return order;    }        public Position getSeat() {        return seat;    }        public int getDi() {        return di;    }        public int getValue() {        return value;    }        public void setDi(int di) {        this.di = di;    }    }class MyStack
     
       {//定义栈结构    private static int index = -1;    private ArrayList
      
        array;    public MyStack() {        array = new ArrayList
       
        ();    }        public void push(T item) {            array.add(item);        index++;    }        public T pop() {        T result = array.get(index);        array.remove(index);        index--;        return result;    }        public boolean isEmpty() {        if(index != -1)            return false;        else             return true;    }}public class MatrixPath {    private static boolean[][] footPrints;    //留下脚印    private static boolean[][] endPrints;    //留下不能通过印记    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        String line = scan.nextLine();    //输入行和列        String[] lines = line.split("\\s+");//分离行和列        int row = Integer.parseInt(lines[0]);        int col = Integer.parseInt(lines[1]);                int[][] matrix = new int[row + 2][col + 2];    //将外层包围一层0元素        footPrints = new boolean[row + 2][col + 2];        endPrints = new boolean[row + 2][col + 2];                  for(int i = 0; i < row; i++) {    //初始化数组元素            line = scan.nextLine();            lines = line.split("\\s");            for(int j = 0; j < lines.length; j++) {                matrix[i + 1][j + 1] = Integer.parseInt(lines[j]);            }        }                scan.close();                int startX = 1;    //入口横坐标        int startY = 1;    //入口纵坐标                System.out.println(exsitPath(startX, startY, row, col, matrix) + " ");        //System.out.println(exsitPath(startX, startY, matrix) + " ");        }        //判断是否存在路径    public static boolean exsitPath(int x, int y, int[][] matrix) {                MyStack
        
          stack = new MyStack
         
          ();        //当前的位置        Position curPos = new Position(x, y);        //开始第一步        int curStep = 1;               do {            if(pass(curPos, matrix)) { //该位置是可通过的                System.out.println("x - y = " + curPos.getX() + " - " + curPos.getY());                footPrint(curPos);//留下脚印                Item item = new Item(curStep, curPos, matrix[curPos.getX()][curPos.getY()], 1);                stack.push(item);//将该可通位置放入栈中                if(item.getValue() == 9) {//如果已经找到目标，则返回                    System.out.println("总共花费了" + curStep + "步, 找到目标");                    return true;                }                curPos = nextPos(curPos, 1);//试探下一步，即东边的，但是不放入栈中                curStep++;//步数加1                            } else {//改位置不可通过                if(!stack.isEmpty()) {//栈不为空                    Item item = stack.pop();//出栈                    while(item.getDi() == 4 && !stack.isEmpty()) {//留下了脚印的个数加上不可通过的个数之和为4，进行出栈处理                        markPrint(item.getSeat());//留下不可通过印记并进行出栈处理                        item = stack.pop();//出栈                    }                    if(item.getDi() < 4) {//四个方向还未试探完                        item.setDi(item.getDi() + 1);//换下一个方向进行试探                        stack.push(item);//入栈                        curPos = nextPos(item.getSeat(), item.getDi());//试探下一个位置                    }                }            }        } while(!stack.isEmpty());            System.out.println("总共花费了" + curStep + "步,没有找到目标");        return false;    }        public static boolean pass(Position curPos, int[][] matrix) {        if(matrix[curPos.getX()][curPos.getY()] != 0 && endPrints[curPos.getX()][curPos.getY()] == false && footPrints[curPos.getX()][curPos.getY()] == false)            return true;        else            return false;    }        public static void footPrint(Position curPos) {        footPrints[curPos.getX()][curPos.getY()] = true;    }        public static Position nextPos(Position curPos, int di) {        int x = curPos.getX();        int y = curPos.getY();        switch(di) {        case 1: {            y = curPos.getY() + 1; //东        }        break;        case 2: {            x = curPos.getX() + 1; //南        }        break;        case 3: {            y = curPos.getY() - 1; //西        }        break;        case 4: {            x = curPos.getX() - 1; //北        }        break;                }                return new Position(x, y);    }        public static void markPrint(Position seat) {        endPrints[seat.getX()][seat.getY()] = true;    }}