非递归实现回溯走迷宫

• 大多数都是递归？我本人喜欢迭代，其实递归肯定可以转迭代的，借助入栈退栈实现，事实上这也是计算机递归底层的原理。数据结构C语言版清华教材栈那一章有个走迷宫，和这个一样原理。对任意一个格子查找上下左右是否有符合的字符，没有就标记已经走过（借助辅助数组）然后退栈，换个方向继续搜索，思路很简单。只要注意边界条件就行了。

import java.util.Stack;
public class Solution {
    private static int col;
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        col = cols;
        if(matrix.length==0||str.length==0||str.length>matrix.length) return false;
        for (int total = 0; total < matrix.length; total++) {
            if (matrix[total] == str[0]) {
                if (checkpath(matrix, total, str)) return true;
            }
        }
        return false;
    }
    private static boolean checkpath(char[] matrix, int in, char[] str) {
        if(str.length==1) return matrix[in]==str[0];
        Stack<Integer> sta = new Stack<Integer>();
        sta.push(in);
        int k = 1, i, j, index;
        int back[] = new int[matrix.length];
        back[in] = 1;
        boolean findflag;
        while (!sta.empty()) {
            index = sta.peek();
            findflag = true;
            j=index%col;
            i=(index-j)/col;
            if ((index - col >= 0) && //上
                    back[index - col] == 0 &&
                    matrix[index - col] == str[k]) {
                index -= col;
            } else if ((index + 1 < (i + 1) * col) &&//右
                    (back[index + 1]) == 0 &&
                    matrix[index + 1] == str[k]) {
                index += 1;
            } else if ((index + col < matrix.length)//下
                    && (back[index + col] == 0)
                    && matrix[index + col] == str[k]) {
                index += col;
            } else if ((index - 1 >= i * col) &&//左
                    (back[index - 1] == 0) &&
                    matrix[index - 1] == str[k]) {
                index -= 1;
            } else {
                findflag = false;//没有找到
            }
            if (findflag && back[index] == 0) {
                sta.push(index);
                k++;//字符窜str下标推进
                if (k == str.length) return true;//已经遍历完str
            } else {
                sta.pop();
                k--;
            }
            back[index] = 1;//无论有无都biao'ji
        }
        return false;
    }

}