小红书：笔试题（棋盘最短路径，笔记本草稿栈，迷宫游戏）

1. 棋盘最短路径问题

题目描述：

题目描述：
假设以一个n*m的矩阵作为棋盘，每个棋位对应一个二维坐标 (x, y)。你有一颗棋子位于左上起点(0, 0)，现在需要将其移动到右下底角 (n-1, m-1)，棋子可以向相邻的上下左右位置移动，每个坐标最多只能经过一次。棋盘中散布着若干障碍，障碍物不能跨越，只能绕行，问是否存在到达右下底角的路线？若存在路线，输出所需的最少移动次数；若不存在，输出0。 Input 第一行三个正整数n，m和k，代表棋盘大小与障碍物个数  1< n、m < 100,  k < n*m 第二行至第k+1行，每行为两个整数x和y，代表k个障碍物的坐标。

输入
输入三个正整数n，m和k，代表棋盘大小与障碍物个数  1< n、m < 100,  k < n*m
第二行至第k+1行，每行为两个整数x和y，代表k个障碍物的坐标。

输出
输出从起点到终点的最短路径的长度，如果不存在，即输出0

代码：

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static int min = Integer.MAX_VALUE;
    public static boolean find = false;
    public static void main( String[] args ) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();//障碍
        boolean[][] go = new boolean[n][m];//棋盘
        boolean[][] visit = new boolean[n][m];//走过的痕迹
        //将所有的位置设置为true
        for(int i=0;i<n;i++) {
            Arrays.fill(go[i], true);
        }
        //有棋子障碍处设置为false
        for(int i=0;i<k;i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            go[a][b] = false;
        }
        findPath(0, 0, 0, visit, go, n - 1, m - 1);
        //如果找到了输出结果，没路输出0
        if(find) {
            System.out.println(min);
        }else {
            System.out.println(0);
        }
    }
 
    private static void findPath( int row , int col , int s, boolean[][] visit, boolean[][] go, int targetRow, int targetCol ) {
        if(row == targetRow && col == targetCol) {//到达目标位置
            find = true;
            if(s < min) {
                min = s;
            }
            return;
        }
        if(col < targetCol && !visit[row][col+1] && go[row][col+1]) { // 右
            visit[row][col+1] = true;
            findPath(row, col + 1, s + 1, visit, go, targetRow, targetCol);
            visit[row][col+1] = false;
        }
        if(row < targetRow && !visit[row+1][col] && go[row+1][col]) { // 下
            visit[row+1][col] = true;
            findPath(row + 1, col, s + 1, visit, go, targetRow, targetCol);
            visit[row+1][col] = false;
        }
        if(col > 0 && !visit[row][col-1] && go[row][col-1]) { // 左
            visit[row][col-1] = true;
            findPath(row, col - 1, s + 1, visit, go, targetRow, targetCol);
            visit[row][col-1] = false;
        }
        if(row > 0 && !visit[row-1][col] && go[row-1][col]) { // 上
            visit[row-1][col] = true;
            findPath(row - 1, col, s + 1, visit, go, targetRow, targetCol);
            visit[row-1][col] = false;
        }
    }
}

2. 笔记草稿

代码1,利用栈

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String results = getRealContent(str);
        System.out.println(results);
    }
    public static String getRealContent(String str) {
        StringBuilder sb = new StringBuilder("");
        char flag = '(';
        Stack<Character> stack = new Stack<Character>();
        char[] chars = str.toCharArray();
        //遍历每个数组将其放入栈中
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] =='(') {//入栈
                stack.push(chars[i]);
            }else if (chars[i] ==')') {//弹出和这个)对应的(以及他们中间的内容
                while(!stack.isEmpty() && stack.peek()!= flag){
                    stack.pop();
                }
                stack.pop();
            }else if (chars[i] =='<') {//删除前面的一个内容
                if(!stack.empty() && stack.peek()!=flag){
                    stack.pop();
                }
                
            }else{
                stack.push(chars[i]);
            }
        }
        while(!stack.empty()){
            sb.append(stack.pop());
        }
        
        return sb.reverse().toString();
    }
}

代码2，括号加减

import java.util.Scanner;
 
public class Main {
    public static void main( String[] args ) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String res = "";
        int count = 0, len = s.length();
        for(int i=0;i<len;i++) {
            char c = s.charAt(i);
            if(c == '(') {
                count ++;
            }else if(c == ')') {
                count --;
            }else if(c == '<') {
                if(res.length() > 0 && count == 0 && res.charAt(res.length() - 1) != ')') {
                    res = res.substring(0, res.length() - 1);
                }
            }else if(count == 0) {
                res += c;
            }
        }
        System.out.println(res);
    }
}

3. 迷宫游戏

import java.util.*;
/**
 * 5
 * .#...
 * ..#S.
 * .E###
 * .....
 * .....
 */
public class B {
    static int[][] d = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };
    static int startX = 0;
    static int startY = 0;
    static int endX = 0;
    static int endY = 0;
    static Set<Integer> stepList = new HashSet<>();
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            String line = in.nextLine();
            for (int j = 0; j < n; j++) {
                board[i][j] = line.charAt(j);
                if (board[i][j] == 'S') {
                    startX = i;
                    startY = j;
                } else if (board[i][j] == 'E') {
                    endX = i;
                    endY = j;
                }
            }
        }
 
        shortestLength(board, n);
 
        if (stepList.size() == 0) {
            System.out.println(-1);
            return;
        }
        int minStep = Integer.MAX_VALUE;
        for (Integer integer : stepList) {
            if (integer < minStep) {
                minStep = integer;
            }
        }
        System.out.println(minStep);
 
    }
 
    private static void shortestLength(char[][] board, int n) {
 
        boolean[][] visited = new boolean[n][n];
        visited[startX][startY] = true;
        shortestLength(board, n, startX, startY, 0, visited);
 
    }
 
    private static void shortestLength(char[][] board, int n, int startX, int startY, int step, boolean[][] visited) {
        if (startX == endX && startY == endY) {
            stepList.add(step);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int newX = startX + d[i][0];
            int newY = startY + d[i][1];
            if (newX < 0) {
                newX = n - 1;
            } else if (newX==n) {
                newX = 0;
            }
            if (newY <0) {
                newY = n-1;
            }else if (newY==n){
                newY = 0;
            }
            if (board[newX][newY] !='#' && !visited[newX][newY]) {
                visited[newX][newY] = true;
                shortestLength(board, n, newX, newY, step + 1, visited);
                visited[newX][newY] = false;
            }
        }
    }
 
}