蓝桥杯17年第一题，走迷宫

走格子题目注意点:

• 以左上角为(0,0)点，类似坐标，使用二维数组去操作。
• 如果是求最优问题，比如最短路径和背包最多可以装多少，建议使用动态规划，去掉重复子问题，大数据建议使用动态规划，否则可能会扣分
• 如果是求有多少种走法或路线，建议使用回溯和DSF记录终点的值，直接暴力求解，而且这种问题容量一般固定，不会有限制。

走迷宫是第一题，走出迷宫有四种方式，既i和j越界，这时候记录加一并return就ok，还有防止重复UD 和 RL问题，碰到的时候这条路就走不通了，直接return。就这两个注意点

package com.company;



/*
标题：迷宫

        X星球的一处迷宫游乐场建在某个小山坡上。
        它是由10x10相互连通的小房间组成的。

        房间的地板上写着一个很大的字母。
        我们假设玩家是面朝上坡的方向站立，则：
        L表示走到左边的房间，
        R表示走到右边的房间，
        U表示走到上坡方向的房间，
        D表示走到下坡方向的房间。

        X星球的居民有点懒，不愿意费力思考。
        他们更喜欢玩运气类的游戏。这个游戏也是如此！

        开始的时候，直升机把100名玩家放入一个个小房间内。
        玩家一定要按照地上的字母移动。

        迷宫地图如下：
        ------------
        UDDLUULRUL
        UURLLLRRRU
        RRUURLDLRD
        RUDDDDUUUU
        URUDLLRRUU
        DURLRLDLRL
        ULLURLLRDU
        RDLULLRDDD
        UUDDUDUDLL
        ULRDLUURRR
        ------------

        请你计算一下，最后，有多少玩家会走出迷宫?
        而不是在里边兜圈子。

        请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。
*/


public class Main {

static private int count = 0;

    public static void main(String[] args) {
        // write your code here
        String[][] martrix = new String[10][10];
        //构造好题目的数据，方便测试
        for (int j = 0; j < martrix[0].length; j++) {

            martrix[0][j] = String.valueOf("UDDLUULRUL".charAt(j));
            martrix[1][j] = String.valueOf("UURLLLRRRU".charAt(j));
            martrix[2][j] = String.valueOf("RRUURLDLRD".charAt(j));
            martrix[3][j] = String.valueOf("RUDDDDUUUU".charAt(j));
            martrix[4][j] = String.valueOf("URUDLLRRUU".charAt(j));
            martrix[5][j] = String.valueOf("DURLRLDLRL".charAt(j));
            martrix[6][j] = String.valueOf("ULLURLLRDU".charAt(j));
            martrix[7][j] = String.valueOf("RDLULLRDDD".charAt(j));
            martrix[8][j] = String.valueOf("UUDDUDUDLL".charAt(j));
            martrix[9][j] = String.valueOf("ULRDLUURRR".charAt(j));
        }
        
        for (int i = 0; i < martrix[0].length; i++) {
            for (int j = 0; j < martrix[0].length; j++) {
                jump(i,j,martrix);
            }
        }
        System.out.println(count);
    }

    public static void jump(int i , int j ,String[][] martrix){

        if (i<0||i>9||j<0||j>9){
            count = count + 1;
            return;
        }
        if (martrix[i][j].equals("U"))
        {
            if (i>=1&&martrix[i-1][j].equals("D")){
                ; return;}
            jump(i-1,j,martrix);
        }
        else if (martrix[i][j].equals("D"))
        {
            if (i<=8&&martrix[i+1][j].equals("U")) return;

            jump(i+1,j,martrix);
        }
        else if (martrix[i][j].equals("L"))
        {
            if (j>=1&&martrix[i][j-1].equals("R")) return;

            jump(i,j-1,martrix);
        }
        else if (martrix[i][j].equals("R"))
        {
            if (j<=8&&martrix[i][j+1].equals("L")) return;

            jump(i,j+1,martrix);
        }

    }

}