首页 > 试题广场 >

编程题1

[编程题]编程题1
  • 热度指数:89 时间限制: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
import java.util.*; public class Main { static char[][] map=new char[110][110]; static int next[][]={{1,0},{-1,0},{0,1},{0,-1}}; static int m,n; static int [][][][] visit = new int[60][60][60][60]; public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n=sc.nextInt();
        m=sc.nextInt();
        sc.nextLine(); for(int i=0;i<n;i++) {
            map[i] = sc.nextLine().toCharArray();
        } int r1=0,r2=0,b1=0,b2=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map[i][j]=='S') {
                    r1 = i;
                    r2 = j;
                } if(map[i][j]=='0'){
                    b1=i;
                    b2=j;
                }
            }
        }
        System.out.println(bfs(r1,r2,b1,b2));
    } static int bfs(int r1,int r2,int b1,int b2){
        LinkedList<Node> queue=new LinkedList<>();
        queue.offer(new Node(r1,r2,b1,b2));
        visit[r1][r2][b1][b2]=1; while(queue.size()>0){
            Node t= queue.poll(); if(map[t.bx][t.by]=='E'){ return visit[t.x][t.y][t.bx][t.by]-1;
            } for(int k=0;k<4;k++){ int mx=t.x+next[k][0]; int my=t.y+next[k][1]; //System.out.println(mx+" ---- "+my); if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='#')continue; if(mx==t.bx&&my==t.by){ int mbx=t.bx+next[k][0]; int mby=t.by+next[k][1]; if(mbx>=n||mbx<0||mby<0||mby>=m ||map[mbx][mby]=='#'||visit[mx][my][mbx][mby]!=0)continue;
                    visit[mx][my][mbx][mby]= visit[t.x][t.y][t.bx][t.by]+1;
                    queue.offer(new Node(mx,my,mbx,mby));
                }else{ if(visit[mx][my][t.bx][t.by]!=0)continue;
                    visit[mx][my][t.bx][t.by] = visit[t.x][t.y][t.bx][t.by]+1;
                    queue.offer(new Node(mx,my,t.bx,t.by));
                }
            }
        } return -1;
    } public static class Node { int x, y, bx, by; public Node(int x, int y, int bx, int by) { this.x = x; this.y = y; this.bx = bx; this.by = by;
        }
    }
}
发表于 2021-01-10 22:30:15 回复(0)