剑指offer+leetcode

public class 递归 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //二维数组表示地图
        int[][] map=new int[8][7];
        //使用1表示墙 上下全部置为1
        for(int i=0;i<7;i++) {
            map[0][i]=1;
            map[7][i]=1;
        }
        //左右全部置为1
        for(int i=0;i<8;i++) {
            map[i][0]=1;
            map[i][6]=1;
        }
        //设置挡板
        map[3][1]=1;
        map[3][2]=1;
        //输出地图
        for(int i=0;i<8;i++) {
            for(int j=0;j<7;j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        //使用
        setWay(map, 1, 1);
        //输出
        for(int i=0;i<8;i++) {
            for(int j=0;j<7;j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
       //使用递归回溯找路
    //i j从哪个位置出发；map[6][5]通路找到；约定：当map[i][j]0未走过 2表示可以走 3已经走过，但是不通
    //需要确定策略：下》右》上》左；如果走不通，回溯
    public static boolean setWay(int[][] map,int i,int j) {
        if(map[6][5]==2) {//通路已经找到
            return true;
        }else {
            if (map[i][j]==0) {
                //按照策略走
                map[i][j]=2;//假定可以走
                if(setWay(map, i+1, j)) {//向下走
                    return true;
                }else if(setWay(map, i, j+1)){//向右走
                    return true;
                }else if(setWay(map, i-1, j)) {//向上走
                    return true;
                }else if(setWay(map, i, j-1)) {//向左走
                    return true;
                }else {//走不通
                    map[i][j]=3;
                    return false;
                }
            }else {//map可能是1，2，3
                return false;    
            }
        }