首页 > 试题广场 >

编程题1

[编程题]编程题1
  • 热度指数:43 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有一个推箱子的游戏, 一开始的情况如下图:

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;

..S0.. -> ...S0.

注意不能将箱子推动到'#'上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。


输入描述:
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;


输出描述:
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
示例1

输入

3 6
.S#..E
.#.0..
......

输出

11
利用bfs进行穷举搜索,计算到达终点的最少步数,需要注意的是:人的位置必须到达箱子的上下左右时才可以带着箱子进行相同方向的移动,否则就只能人动箱子不动。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    // 移动矩阵(上下向左右移动时,横纵坐标的改变)
    static int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().trim().split(" ");
        int n = Integer.parseInt(temp[0]), m = Integer.parseInt(temp[1]);
        char[][] maze = new char[n][];
        for(int i = 0; i < n; i++)
            maze[i] = br.readLine().trim().toCharArray();
        // 人的起始位置S以及箱子的位置
        int startX = 0, startY = 0, boxX = 0, boxY = 0;
        // 判断位置,即人要先找到箱子,再推着箱子往前走
        for(int i = 0; i < n; i++){  
            for(int j = 0; j < m; j++){
                if(maze[i][j] == 'S'){
                    // 人开始的位置
                    startX = i;
                    startY = j;
                }
                if(maze[i][j] == '0'){
                    // 箱子的位置
                    boxX = i;
                    boxY = j;
                }
            }
        }
        System.out.println(bfs(maze, startX, startY, boxX, boxY));
    }
    
    private static int bfs(char[][] maze, int startX, int startY, int boxX, int boxY) {
        Node start = new Node(startX, startY, boxX, boxY);
        int n = maze.length;
        int m = maze[0].length;
        // iswalked四维数组,可以用来存储走过的路径以防重复。
        int[][][][] iswalked = new int[n][n][m][m];
        // 每个节点都有4个方向的移动,分别是上下左右
        int[][] moveDirection = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<Node> queue = new LinkedList<>();  // 利用队列实现BFS
        start.step = 0;
        queue.offer(start);
        // 开始BFS广度搜索最短路径
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            int newBx = cur.bx;
            int newBy = cur.by;
            // 向4个方向走
            for(int i = 0; i < 4; i++){
                // 人在箱子的左右上下才能够推箱子,否则箱子的坐标不变
                if(cur.px == cur.bx){
                     if(cur.py + moveDirection[i][1] == cur.by){
                         newBy = cur.by + moveDirection[i][1];
                     }else{
                         newBy = cur.by;
                     }
                }
                if(cur.py == cur.by){
                    if(cur.px + moveDirection[i][0] == cur.bx){
                        newBx = cur.bx + moveDirection[i][0];
                    }else{
                        newBx = cur.bx;
                    }
               }
                // 箱子找到了要随人往4个方向动;没找到则箱子不动人动
                Node next = new Node(cur.px + moveDirection[i][0], cur.py + moveDirection[i][1], newBx, newBy); 
                // 不能让人在没找到箱子之前出地图或者自己提前到目的地
                if(next.px < 0 || next.px  >= n || next.py < 0||next.py >= m 
                   || next.bx < 0||next.bx >= n||next.by < 0||next.by >= m
                   || maze[next.px][next.py] == '#'
                   || maze[next.bx][next.by] == '#'){
                    continue;
                }
                // 0说明这条路径没有走过
                if(iswalked[next.px][next.bx][next.py][next.by] == 0){
                    iswalked[next.px][next.bx][next.py][next.by] = 1;
                    next.step = cur.step + 1;
                    if(maze[next.bx][next.by] == 'E'){
                        // 此时把箱子推到终点了
                        return next.step;  // 最先到终点的就是最短路径
                    }
                    queue.offer(next);
                }
            }
        }
        return -1;
    }
    
    private static class Node{
        // 人的位置
        int px;
        int py;
        // 箱子的位置
        int bx;
        int by;
        // 从初始位置到现在节点所走的步数
        int step;
        public Node(int px, int py, int bx, int by){
            this.px = px;
            this.py = py;
            this.bx = bx;
            this.by = by;
        }
    }
}


发表于 2021-01-27 17:05:03 回复(0)