回溯法

回溯法适合用递归实现。它从解决问题每一步的所有选项选一个可行的执行。进入下一步之后又面临新的选项，当不满足条件时就回到上一个选项继续其它选项，如果所有节点的所有选项都不能满足约束条件的终结状态，则问题无解。

矩阵路径问题

问题描述

设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径，路径可以从距震中的任意一个开始，每一步可以再矩阵中向左右上下移动，已经走过的格子不能重复进入。

问题分析
这个题可以用回溯法来解决，这里选择左上角为第一个格子，下一步可以使左右上下，假如向右走的的(i+1,j)的格子的字符和输入串的第一个匹配，则将输入串的第一个字符去掉，并且在(i+1,j)格子上继续之前的操作，如果此时向下走不匹配则回溯到(i+1,j)继续向其他方向去尝试。直到存在一条路径使得所有尝试都为true，则说明存在这样一条通路整个函数返回true。由于路径不能重复进入格子。还需要定义和字符矩阵一样大的布尔类型矩阵来标识是否已经经过这个格子。

代码实现

import java.util.Scanner;

public class Test12 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        char[][] map = {{'a','b','t','g'},{'c','f','c','s'},{'j','d','e','h'}};
        System.out.println(exsistLine(input,map));
    }
    public static boolean exsistLine(String input,char[][] map){
        if(map==null||map.length==0){ //字符矩阵为空时
            return false;
        }
        boolean isthrough[][]  = new boolean[map.length][map[0].length];
        for(int i =0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                isthrough[i][j] = false; 
            }
        }
        for(int i=0;i<map.length;i++){//从左上角开始
            for(int j=0;j<map[0].length;j++){
                if(exsistLineCore(input, i, j, map, isthrough)){
                    return true;
                }
            }
        }       
        return false;
    }
    public static boolean exsistLineCore(String input,int i,int j,char[][] map,boolean[][] isthrough){
        String temp = input;
        boolean hasPath = false;
        //当input.length()<=0的时候说明所有字符已经匹配完毕
        if(input.length()<=0){
            return true;
        }
        if(i>=0&&j>=0&&i<map.length&&j<map[0].length){
            if(input.length()>0&&map[i][j]==input.charAt(0)&&!isthrough[i][j]){  //匹配
                input=input.substring(1, input.length());
                isthrough[i][j]=true;
                //向四周走
                hasPath = exsistLineCore(input, i+1, j, map, isthrough)||
                exsistLineCore(input, i-1, j, map, isthrough)||
                exsistLineCore(input, i, j+1, map, isthrough)||
                exsistLineCore(input, i, j-1, map, isthrough);
            
            }
        }else{
            //一旦出现不匹配就回溯将布尔矩阵置为false
            if(i>=0&&j>=0&&i<map.length&&j<map[0].length){
                isthrough[i][j]=false;
            }
            return false;
        }
        return hasPath;
        
    }
}

当符合要求的递归调用完成后这个递归的最终返回值必定为true，此时找到这条路径，如果所有递归调用的最终结果都不满足则说明没有这条路径。