编程题1

[编程题]编程题1

热度指数：3993 时间限制：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..
......

输出

算法知识视频讲解

Java

渡口的小太阳

bfs,注意找到箱子后和箱子一起移动

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        char[][] chas=new char[n][m];
        int startX=0,startY=0,boxX=0,boxY=0;
        for(int i=0;i<n;i++){
            String string=sc.next();
            for(int j=0;j<m;j++){
                chas[i][j]=string.charAt(j);
                if(chas[i][j]=='S'){
                    startX=i;
                    startY=j;
                }
                if(chas[i][j]=='0'){
                    boxX=i;
                    boxY=j;
                }
            }
        }
        System.out.println(bfsMinStep(chas,startX,startY,boxX,boxY));
    }

    public static class Node{
        int x;
        int y;
        int bx;
        int by;
        int step;
        public Node(int x,int y,int bx,int by){
            this.x=x;
            this.y=y;
            this.bx=bx;
            this.by=by;
        }
    }
    private static int bfsMinStep(char[][] chas,int startX, int startY,int boxX,int boxY) {
        Node start=new Node(startX, startY,boxX,boxY);
        int n=chas.length;
        int m=chas[0].length;
        boolean[][][][] isVisted=new boolean[n][m][n][m];
        
        int[][] dir=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
        Queue<Node> queue=new LinkedList<>();
        start.step=0;
        queue.add(start);
        while(!queue.isEmpty()){
            Node cur=queue.poll();
            int newBx=cur.bx;
            int newBy=cur.by;
            for(int i=0;i<4;i++){
                            //在箱子上面或下面
                if(cur.y==cur.by){
                     newBx=cur.x+dir[i][0]==cur.bx?cur.bx+dir[i][0]:cur.bx;
                }
                            //在箱子左边或右边
                if(cur.x==cur.bx){
                     newBy=cur.y+dir[i][1]==cur.by?cur.by+dir[i][1]:cur.by;    
                }
                Node next=new Node(cur.x+dir[i][0], cur.y+dir[i][1],newBx,newBy);
                if(next.x<0||next.x>=n||next.y<0||next.y>=m||chas[next.x][next.y]=='#'
                        ||next.bx<0||next.bx>=n||next.by<0||next.by>=m
                        ||chas[next.bx][next.by]=='#'){
                    continue;
                }
                if(!isVisted[next.x][next.y][next.bx][next.by]){
                    isVisted[next.x][next.y][next.bx][next.by]=true;
                    next.step=cur.step+1;
                    if(chas[next.bx][next.by]=='E'){
                        return next.step;
                    }
                    queue.add(next);
                }
            }
        }
        return -1;
    }
}

发表于 2019-04-23 22:39:15 回复(1)