笔试测试

2021-03-23

字数统计: 2.5k字 | 阅读时长≈ 13分

记录下被问到的题目~

第一题走迷宫

import org.jetbrains.annotations.Nullable;

import java.util.Objects;
import java.util.Stack;

/**
 * @Auther GermMC
 * @Date 2021/3/23-14:34
 * @Idea 实现思路 便利矩阵 找到小人位置 然后利用深度优先原则搜索周围的出口 直到数组边界
 * @Aim
 */
public class Exam1 {

    public static void main(String[] args) {
        char[][] matrix = new char[][]{
                {1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 1, 0, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 0, 1},
                {1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
                {1, 0, 1, 1, 0, 1, 0, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 0, 0, 0, 1},
                {1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, '%', 0, 0, 1, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
        };
        int rowPos = -1;
        int columnPos = -1;
        //找到小人
        for (int rowIndex = 0; rowIndex < matrix.length; rowIndex++) {
            for (int columnIndex = 0; columnIndex < matrix[rowIndex].length; columnIndex++) {
                if (matrix[rowIndex][columnIndex] == '%') {
                    rowPos = rowIndex;
                    columnPos = columnIndex;
                    break;
                }
            }
        }
        //如果迷宫中没有发现小人
        if (rowPos == -1) {
            throw new NullPointerException("没有人被困在迷宫中~");
        }
        Stack<Point> resultStack = new Stack<>();
        Stack<Point> pathStack = new Stack<>();
        //如果找到了迷宫出口
        if (depthRecursion(resultStack, pathStack, new Point(rowPos, columnPos), matrix, null)) {
            System.out.println("出迷宫路线为 ");
            int i = 1;
            while (!resultStack.empty()) {
                Point pop = resultStack.pop();
                //打印出正确步骤
                System.out.println("第" + i + "步 前往坐标 " + pop.getX() + " " + pop.getY());
                //替换迷宫路线
                matrix[pop.getX()][pop.getY()] = '#';
                i++;
            }
            System.out.println("恭喜你成功走出去了~");
            System.out.println();
            System.out.println("现在我们看下迷宫的鸟瞰图~");
            for (int rowIndexOut = 0; rowIndexOut < matrix.length; rowIndexOut++) {
                for (int columnIndexOut = 0; columnIndexOut < matrix[rowIndexOut].length; columnIndexOut++) {
                    char pos = matrix[rowIndexOut][columnIndexOut];
                    System.out.print((pos == 1 || pos == 0) ? String.valueOf((int) pos) : pos);
                    System.out.print(" ");
                }
                System.out.println();
            }
        } else {
            System.out.println("这个迷宫是个死胡同...");
        }
    }


    /**
     * @param resultPath 路线结果栈
     * @param nowPath    当前走过的路 (主要防止产生无限递归)
     * @param point      目标点
     * @param matrix     迷宫
     * @param from       从什么方向到这个点的
     * @return 是否有出口
     */
    private static boolean depthRecursion(Stack<Point> resultPath, Stack<Point> nowPath, Point point, char[][] matrix, @Nullable DirectionNode from) {
        for (DirectionNode node : DirectionNode.values()) {
            //不用查询来的方向了
            if (from != null && from == node) continue;
            if (node.directionCall.getResultType(point.getX(), point.getY(), matrix) == ResultType.BORDER) {
                //发现边界游戏结束
                return true;
            } else if (node.directionCall.getResultType(point.getX(), point.getY(), matrix) == ResultType.WALL) {
                //发现墙壁什么也不干 寻找下个子树
            } else if (node.directionCall.getResultType(point.getX(), point.getY(), matrix) == ResultType.ROAD) {
                //发现可行的路
                Point nextPoint = node.directionCall.getNextPoint(point.getX(), point.getY());
                //如果已经存在 说明走过这里了 不要绕圈圈
                if (nowPath.contains(nextPoint)) {
                    System.out.println("发现已经走过的路");
                    continue;
                }
                //可以走一波~
                nowPath.push(nextPoint);
                System.out.println("现在在位置 " + point.getX() + " " + point.getY() + " 向 " + node + " 到坐标 " + nextPoint.toString());
                //在找到的下个点继续搜索
                boolean findSuccess = depthRecursion(resultPath, nowPath, nextPoint, matrix, DirectionNode.getReverse(node));
                if (findSuccess) { //寻找成功
                    resultPath.push(nextPoint);
                    return true;
                }
            }
        }
        //退点
        if (!nowPath.empty()) nowPath.pop();
        return false;
    }

    private static class Point {
        final int x;
        final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public String toString() {
            return "x=" + x + ", y=" + y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    //根据方向列出四个节点
    private enum DirectionNode {
        UP(new DirectionCall() { //上移一行
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex - 1, columnIndex);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, char[][] matrix) {
                return rowIndex - 1 < 0 ? ResultType.BORDER : matrix[rowIndex - 1][columnIndex] == 0 ? ResultType.ROAD : ResultType.WALL;
            }
        }),
        DOWN(new DirectionCall() { //下移一行
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex + 1, columnIndex);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, char[][] matrix) {
                //如果下一行大于数组行长度 那么返回边界 否则如果为0返回路 否则返回墙壁
                return rowIndex + 1 >= matrix.length ? ResultType.BORDER : matrix[rowIndex + 1][columnIndex] == 0 ? ResultType.ROAD : ResultType.WALL;
            }
        }),
        LEFT(new DirectionCall() { //左移动一列
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex, columnIndex - 1);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, char[][] matrix) {
                return columnIndex - 1 < 0 ? ResultType.BORDER : matrix[rowIndex][columnIndex - 1] == 0 ? ResultType.ROAD : ResultType.WALL;
            }
        }), RIGHT(new DirectionCall() { //右移动一列
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex, columnIndex + 1);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, char[][] matrix) {
                return columnIndex + 1 >= matrix[columnIndex].length ? ResultType.BORDER : matrix[rowIndex][columnIndex + 1] == 0 ? ResultType.ROAD : ResultType.WALL;
            }
        });

        DirectionCall directionCall;

        DirectionNode(DirectionCall directionCall) {
            this.directionCall = directionCall;
        }

        /**
         * @param directionNode 朝向
         * @return 反向
         */
        public static DirectionNode getReverse(DirectionNode directionNode) {
            if (directionNode == LEFT) {
                return RIGHT;
            } else if (directionNode == RIGHT) {
                return LEFT;
            } else if (directionNode == UP) {
                return DOWN;
            } else if (directionNode == DOWN) {
                return UP;
            }
            throw new RuntimeException("方向节点未知 " + directionNode);
        }

        interface DirectionCall {
            Point getNextPoint(int rowIndex, int columnIndex);

            ResultType getResultType(int rowIndex, int columnIndex, char[][] matrix);
        }
    }

    /**
     * 目标点的类型
     */
    private enum ResultType {
        WALL, ROAD, BORDER;
    }

}

输出的结果

第二题连锁破坏

import org.jetbrains.annotations.Nullable;

import java.util.Objects;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @Auther GermMC
 * @Date 2021/3/23-16:07
 * @Idea
 * @Aim
 */
public class Exam2 {
    public static void main(String[] args) {
        //需要破坏的方块矩阵
        char[][] matrix = new char[][]{
                {1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 1, 0, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 0, 1},
                {1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
                {1, 0, 1, 1, 0, 1, 0, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 0, 0, 0, 1},
                {1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 0, 1, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
        };


        //模拟方块的随机分布
        for (int row = 0; row < matrix.length; row++) {
            for (int column = 0; column < matrix[row].length; column++) {
                int i = ThreadLocalRandom.current().nextInt(2);
                matrix[row][column] = (char) i;
            }
        }

        destory(4, 5, matrix);
    }

    public static void destory(int blockX, int blockY, char[][] matrix) {
        if (blockX < 0 || matrix.length <= blockX) {
            throw new RuntimeException("要破坏的方块不在该矩阵内");
        }
        if (blockY < 0 || matrix[blockX].length <= blockY) {
            throw new RuntimeException("要破坏的方块不在该矩阵内");
        }
        //打印方块矩阵
        System.out.println("我们先看一下方块分布图");
        for (int rowIndexOut = 0; rowIndexOut < matrix.length; rowIndexOut++) {
            for (int columnIndexOut = 0; columnIndexOut < matrix[rowIndexOut].length; columnIndexOut++) {
                char pos = matrix[rowIndexOut][columnIndexOut];
                System.out.print((pos == '#') ? pos : String.valueOf((int) pos));
                System.out.print(" ");
            }
            System.out.println();
        }
        //获取要破坏的方块材质
        int targetBlockTypeId = matrix[blockX][blockY];
        System.out.println("准备破坏方块类型 " + targetBlockTypeId);
        Point sourcePoint = new Point(blockX, blockY);
        Stack<Point> resultStack = new Stack<>();
        //获取要破坏的方块
        depthRecursion(targetBlockTypeId, resultStack, sourcePoint, matrix, null);
        int i = 0;
        while (!resultStack.empty()) {
            Point pop = resultStack.pop();
            //替换破坏方块的矩阵
            matrix[pop.getX()][pop.getY()] = '#';
            i++;
        }
        System.out.println();
        System.out.println("方块破坏成功~ ");
        System.out.println("你一共破坏了 " + i + " 个方块");
        System.out.println("现在我们看下破坏的方块的鸟瞰图~");
        for (int rowIndexOut = 0; rowIndexOut < matrix.length; rowIndexOut++) {
            for (int columnIndexOut = 0; columnIndexOut < matrix[rowIndexOut].length; columnIndexOut++) {
                char pos = matrix[rowIndexOut][columnIndexOut];
                System.out.print((pos == '#') ? pos : String.valueOf((int) pos));
                System.out.print(" ");
            }
            System.out.println();
        }

    }

    /**
     * @param resultPath 路线结果栈
     * @param point      目标点
     * @param matrix     迷宫
     * @param from       从什么方向到这个点的
     * @return 是否有出口
     */
    private static void depthRecursion(int descID, Stack<Point> resultPath, Point point, char[][] matrix, @Nullable DirectionNode from) {
        //遍历点周围的四个子树  贪婪的吃掉周围所有相同值的点
        for (DirectionNode node : DirectionNode.values()) {
            //不用查询来的方向了
            if (from != null && from == node) continue;
            if (node.directionCall.getResultType(point.getX(), point.getY(), descID, matrix) == ResultType.BORDER) {
                //发现边界什么也不干 等待寻找下个子树
            } else if (node.directionCall.getResultType(point.getX(), point.getY(), descID, matrix) == ResultType.WALL) {
                //发现墙壁什么也不干 寻找下个子树
            } else if (node.directionCall.getResultType(point.getX(), point.getY(), descID, matrix) == ResultType.DESC_BLOCK) {
                //发现可行的路
                Point nextPoint = node.directionCall.getNextPoint(point.getX(), point.getY());
                //如果已经存在 说明走过这里了 不要绕圈圈
                if (resultPath.contains(nextPoint)) {
                    continue;
                }
                //可以走一波~
                resultPath.push(nextPoint);
                //在找到的下个点继续搜索
                depthRecursion(descID, resultPath, nextPoint, matrix, DirectionNode.getReverse(node));
            }
        }
    }

    private static class Point {
        final int x;
        final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public String toString() {
            return "x=" + x + ", y=" + y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    //根据方向列出四个节点
    private enum DirectionNode {
        UP(new DirectionCall() { //上移一行
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex - 1, columnIndex);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, int descID, char[][] matrix) {
                return rowIndex - 1 < 0 ? ResultType.BORDER : matrix[rowIndex - 1][columnIndex] == descID ? ResultType.DESC_BLOCK : ResultType.WALL;
            }
        }),
        DOWN(new DirectionCall() { //下移一行
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex + 1, columnIndex);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, int descID, char[][] matrix) {
                //如果下一行大于数组行长度 那么返回边界 否则如果为0返回路 否则返回墙壁
                return rowIndex + 1 >= matrix.length ? ResultType.BORDER : matrix[rowIndex + 1][columnIndex] == descID ? ResultType.DESC_BLOCK : ResultType.WALL;
            }
        }),
        LEFT(new DirectionCall() { //左移动一列
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex, columnIndex - 1);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, int descID, char[][] matrix) {
                return columnIndex - 1 < 0 ? ResultType.BORDER : matrix[rowIndex][columnIndex - 1] == descID ? ResultType.DESC_BLOCK : ResultType.WALL;
            }
        }), RIGHT(new DirectionCall() { //右移动一列
            @Override
            public Point getNextPoint(int rowIndex, int columnIndex) {
                return new Point(rowIndex, columnIndex + 1);
            }

            @Override
            public ResultType getResultType(int rowIndex, int columnIndex, int descID, char[][] matrix) {
                return columnIndex + 1 >= matrix[columnIndex].length ? ResultType.BORDER : matrix[rowIndex][columnIndex + 1] == descID ? ResultType.DESC_BLOCK : ResultType.WALL;
            }
        });

        DirectionCall directionCall;

        DirectionNode(DirectionCall directionCall) {
            this.directionCall = directionCall;
        }

        /**
         * @param directionNode 朝向
         * @return 反向
         */
        public static DirectionNode getReverse(DirectionNode directionNode) {
            if (directionNode == LEFT) {
                return RIGHT;
            } else if (directionNode == RIGHT) {
                return LEFT;
            } else if (directionNode == UP) {
                return DOWN;
            } else if (directionNode == DOWN) {
                return UP;
            }
            throw new RuntimeException("方向节点未知 " + directionNode);
        }

        interface DirectionCall {
            Point getNextPoint(int rowIndex, int columnIndex);

            ResultType getResultType(int rowIndex, int columnIndex, int descID, char[][] matrix);
        }
    }

    /**
     * 目标点的类型
     */
    private enum ResultType {
        WALL, DESC_BLOCK, BORDER;
    }
}

输出的结果

本文作者： GermMC
本文链接： http://blog.germmc.com/2021/03/23/test/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！

记录下被问到的题目~

第一题 走迷宫

输出的结果

第二题 连锁破坏

输出的结果

第一题走迷宫

第二题连锁破坏