首页 > 试题广场 >

推箱子

[编程题]推箱子

热度指数：3161 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。

输入描述:

每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。

输出描述:

输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。

示例1

输入

4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...

输出

3
11

算法知识视频讲解

Java

陈祯飞

import java.util.*;
public class Main{
    public static void main(String...args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        char[][] map = new char[N+2][M+2];
        boolean[][]used = new boolean[N+2][M+2];
        for(int i=0;i<map.length;i++){
            Arrays.fill(map[i], '#');
        }

        int[] start = null;
        int[] end = null;
        int[] box = null;
        for(int i=1;i<map.length-1;i++){
            int j=1;
            for(char ch: scan.next().toCharArray()) {
                map[i][j] = ch;
                if (ch == 'X') {
                    start = new int[]{i, j};
                }
                if (ch == '@') {
                    end = new int[]{i, j};
                }
                if (ch == '*') {
                    box = new int[]{i, j};
                }
                j++;
            }
        }
        int res = findWay(map, used, start, end, box, 0);
        System.out.println(res);
    }
    private static int findWay(char[][]map, boolean[][]used, int[] start, int[] end, int[] box, int wayLen){
        if(box[0] == end[0] && box[1] == end[1]){
            return wayLen;
        }
        else{
            int res = Integer.MAX_VALUE;
            int[]curbox = box.clone();
            int[][]dirs = new int[][]{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//left, up, right, down;
            for(int[] dir: dirs){
                int[] next = new int[]{start[0]+dir[0], start[1]+dir[1]};
                if(used[next[0]][next[1]] || map[next[0]][next[1]] == '#'){
                    continue;
                }
                if(next[0] == box[0] && next[1] == box[1]){
                    curbox = new int[]{box[0]+dir[0], box[1]+dir[1]};
                    if(used[curbox[0]][curbox[1]] || map[curbox[0]][curbox[1]] == '#'){
                        continue;
                    }
                }

                used[next[0]][next[1]] = true;
                //System.out.println("next: "+Arrays.toString(next));
                int curLen = findWay(map, used, next, end, curbox, wayLen+1);
                used[next[0]][next[1]] = false;

                res = curLen == -1? res: Math.min(res, curLen);
            }
            return res == Integer.MAX_VALUE? -1: res;
        }
    }
}

发表于 2017-06-14 21:13:50 回复(0)