有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
一个数字,表示最少几步能完成游戏,如果不能,输出-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;
}
}
}