面试12：矩阵中的路径
* 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
* 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左，右，上，下移动一格。
* 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3X4的矩阵中
* 包含一条字符串"bfce"的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串"abfb"的路径，
* 因为字符串的第一个字符b占据了矩阵的第一行第二个格子之后，路径不能再次进入这个格子。

package com.cloud.algorithm.demo;

import org.junit.Test;
import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * DATE: 2021/4/1
 * Author: xiaoqu
 * Version: 1.0.0
 * 回溯法
 */
public class Topic12 {

    /**
     * 面试12：矩阵中的路径
     * 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
     * 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左，右，上，下移动一格。
     * 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3X4的矩阵中
     * 包含一条字符串"bfce"的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串"abfb"的路径，
     * 因为字符串的第一个字符b占据了矩阵的第一行第二个格子之后，路径不能再次进入这个格子。
     * a b t g
     * c f c s
     * j d e h
     */
    @Test
    public void topic12_1(){
        char[] originalArr={'a','b','t','g','c','f','c','s','j','d','e','h'};
        char[] detArr={'b','f','c','e','d','f'};
        int rows=3;
        int cols=4;
        Map userData = new HashMap();
        for(int row=0;row<rows;row++){
             for(int col=0;col<cols;col++){
                 boolean isExists = this.hasPath(originalArr, detArr, rows, cols, row, col, userData,0);
                    if(isExists){
                        System.out.println("--------- have finded--------");
                       return;
                    }
             }
         }
    }

    private boolean hasPath(char[] originalArr, char[] detArr, int rows, int cols, int row, int col, Map userData,int desIdx){
        int desNum=row * cols + col;
        String str = (String) userData.get(desNum);
        //当索引越界或者已经该元素已经出现在之前步骤中，停止查找，直接返回不符合
        if(row<0||col<0||row>=rows||col>=cols|| !StringUtils.isEmpty(str)){
            return  false;
        }
        //当目标索引和寻找的字符串长度一样，停止查找
        if(desIdx>=detArr.length){
            return true;
        }
        if(originalArr[desNum] ==detArr[desIdx]){
            userData.put(desNum,originalArr[desNum]+"");

            //如果此元素符合条件，依次找他的上下左右节点是否符合，如果符合返回成功，如果不符合则删除这个元素站位，遍历下一个元素
            boolean up = this.hasPath(originalArr, detArr, rows, cols, row-1, col, userData, desIdx+1);
            if(up){
                return true;
            }
            boolean dowm = this.hasPath(originalArr, detArr, rows, cols, row+1, col, userData, desIdx+1);
            if(dowm){
                return true;
            }
            boolean left = this.hasPath(originalArr, detArr, rows, cols, row, col-1, userData, desIdx+1);
            if(left){
                return true;
            }
            boolean right = this.hasPath(originalArr, detArr, rows, cols, row, col+1, userData, desIdx+1);
            if(right){
                return true;
            }
            userData.remove(desNum);
        }
        return false;
    }
}