有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 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
#include <bits/stdc++.h> using namespace std; const int N = 51; int dir[4][2]={{0,-1}, {0,1}, {-1,0}, {1,0}}; bool vis[N][N][N][N]; char G[N][N]; struct P{ int sx, sy, bx, by, t; }; int main(){ int n, m, s=-1; scanf("%d%d", &n, &m); P p; p.t = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ cin>>G[i][j]; if(G[i][j] == 'S'){ p.sx = i; p.sy = j; }else if(G[i][j]=='0'){ p.bx = i; p.by = j; } } vis[p.sx][p.sy][p.bx][p.by] = true; queue<P> q; q.push(p); while(!q.empty() && s==-1){ p = q.front(); q.pop(); if(p.t > 1000) break; for(int i=0;i<4 && s==-1;i++){ int sx = p.sx + dir[i][0]; int sy = p.sy + dir[i][1]; int bx, by; if(sx<0 || sx>=n || sy<0 || sy>=m || G[sx][sy]=='#') continue; if(sx==p.bx && sy==p.by){ bx = p.bx + dir[i][0]; by = p.by + dir[i][1]; if(G[bx][by]=='E') s = p.t + 1; }else{ bx = p.bx; by = p.by; } if(!vis[sx][sy][bx][by]){ vis[sx][sy][bx][by] = true; q.push(P{sx, sy, bx, by, p.t+1}); } } } printf("%d\n", s); return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); Main main = new Main(); //行 int rlen = sc.nextInt(); //列 int llen = sc.nextInt(); String[] strs = new String[rlen]; for(int i = 0; i < rlen; i++){ strs[i] = sc.next(); } char[][] grid = new char[rlen][llen]; //O(mn) 查找 人物坐标、箱子坐标 int px = 0, py = 0, bx = 0, by = 0; for(int i = 0; i < rlen; i++){ for(int j = 0; j < llen; j++){ grid[i][j] = strs[i].charAt(j); if(grid[i][j] == 'S'){ px = i; py = j; } if(grid[i][j] == '0'){ bx = i; by = j; } } } System.out.println(main.helper(grid, px, py, bx, by)); } private int helper(char[][] grid, int px, int py, int bx, int by){ int rlen = grid.length; int llen = grid[0].length; //visited[i][j][m][n] = true 表示 人物在 (i, j) 坐标和 箱子在 (m, n) 坐标 这个状态已经访问过了 boolean[][][][] visited = new boolean[rlen][llen][rlen][llen]; /* 当人物在箱子的左边时,人物可以选择向右边走 当人物在箱子的右边时,人物可以选择向左边走 当人物在箱子的上边时,人物可以选择向下边走 当人物在箱子的下边时,人物可以选择向上边走 这样才能保证步数最少,否则,如果箱子在左边,人物还向着右边走,那么就距离箱子越来越远,这是毫无意义的步数 什么时候箱子的位置会发生改变? 当人物向上下两个方向走的时候,如果人物的下一个位置就是箱子的位置, 那么相当于顶着箱子前进,那么箱子同时也要往前进 */ ;int[][] pos = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} Queue<Node> queue = new ArrayDeque<>(); queue.add(new Node(px, py, bx, by)); int step = 0; while(!queue.isEmpty()){ int size = queue.size(); while(size-- > 0){ Node node = queue.poll(); if(grid[node.bx][node.by] == 'E'){ return step; } //往四个方向走 for(int[] p : pos){ int newPx = node.px + p[0]; int newPy = node.py + p[1]; int newBx = node.bx; int newBy = node.by; //人物的前进位置刚好是箱子的位置,那么箱子的位置也要发生改变 if(newPx == node.bx && newPy == node.by){ newBx += p[0]; newBy += p[1]; } //越界或者在障碍物上,那么跳过 if(newPx < 0 || newPx == rlen || newPy < 0 || newPy == llen || newBx < 0 || newBx == rlen || newBy < 0 || newBy == llen || grid[newPx][newPy] == '#' || grid[newBx][newBy] == '#'){ continue; } if(!visited[newPx][newPy][newBx][newBy]){ visited[newPx][newPy][newBx][newBy] = true; queue.add(new Node(newPx, newPy, newBx, newBy)); } } } step++; } return -1; } class Node{ //人物坐标 int px; int py; //箱子坐标 int bx; int by; public Node(int px, int py, int bx, int by){ this.px = px; this.py = py; this.bx = bx; this.by = by; } } }
#include <bits/stdc++.h> using namespace std; const int N = 55; bool vis[N][N][N][N]; /// vis[a][b][c][d] 表示人在 (a,b)处, char maze[N][N]; int n,m,px,py,boxx,boxy,ex,ey; struct Node{ int px,py,boxx,boxy,step; bool operator < (const Node& rs) const{ /// 重载, step大的Node优先级小 return rs.step < step; } }s; int dir[][2] = {1,0,-1,0,0,1,0,-1}; bool judge(int x,int y){ if(x < 0 || x>=n || y<0||y>=m || maze[x][y]=='#') return false; return true; } int bfs(){ s = {px,py,boxx,boxy,0}; priority_queue<Node> q; q.push(s); vis[px][py][boxx][boxy] = 1; while(!q.empty()){ Node u = q.top();q.pop(); //printf("%d %d %d %d\n",u.px,u.py,u.boxx,u.boxy); if(u.boxx ==ex && u.boxy == ey) return u.step; for(int i=0;i<4;i++){ int pxx = u.px + dir[i][0]; int pyy = u.py + dir[i][1]; /// 人往该方向走了一步 int boxx = u.boxx,boxy = u.boxy; if(pxx == boxx && pyy == boxy) { /// 碰到了箱子则将箱子向外推动一格 boxx += dir[i][0]; boxy += dir[i][1]; } if(!judge(pxx,pyy) || !judge(boxx,boxy)) continue; if(vis[pxx][pyy][boxx][boxy]) continue; vis[pxx][pyy][boxx][boxy] = 1; q.push({pxx,pyy,boxx,boxy,u.step+1}); } } return -1; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",maze[i]); for(int j=0;j<m;j++){ if(maze[i][j]=='0') boxx = i,boxy = j,maze[i][j]='.'; if(maze[i][j]=='S') px = i,py = j,maze[i][j]='.'; if(maze[i][j]=='E') ex = i,ey = j,maze[i][j]='.'; } } printf("%d\n",bfs()); return 0; }
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
new Main().solute();
}
public void solute() {
Scanner sc = new Scanner(System.in);
// m n
int m = sc.nextInt();
int n = sc.nextInt();
sc.nextLine();
// maze
String[] input = new String[m];
for (int i = 0; i < m; i++) {
input[i] = sc.nextLine();
}
char[][] maze = new char[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maze[i][j] = input[i].charAt(j);
}
}
bfs(m, n, maze);
}
public void bfs(int m, int n, char[][] maze) {
int[][][][] arr = new int[m][n][m][n];
Queue<int[]> queue = new LinkedList<>();
// find S, box, E
int sX = 0, sY = 0, bX = 0, bY = 0, eX = 0, eY = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] == 'S') {
sX = i;
sY = j;
}
if (maze[i][j] == '0') {
bX = i;
bY = j;
}
if (maze[i][j] == 'E') {
eX = i;
eY = j;
}
}
}
queue.offer(new int[]{sX, sY, bX, bY});
while (queue.peek() != null) {
int[] poll = queue.poll();
int sNowX = poll[0];
int sNowY = poll[1];
int bNowX = poll[2];
int bNowY = poll[3];
for (int i = 0; i < 4; i++) {
int snx = sNowX + theX[i];
int sny = sNowY + theY[i];
int bnx = snx + theX[i];
int bny = sny + theY[i];
if (snx >= 0 && sny >= 0 && snx < m && sny < n && maze[snx][sny] != '#' &&
(snx != bNowX || sny != bNowY) &&
arr[snx][sny][bNowX][bNowY] == 0) {
arr[snx][sny][bNowX][bNowY] = arr[sNowX][sNowY][bNowX][bNowY] + 1;
queue.offer(new int[]{snx, sny, bNowX, bNowY});
} else if (snx == bNowX && sny == bNowY &&
bnx >= 0 && bny >= 0 && bnx < m && bny < n && maze[bnx][bny] != '#' &&
arr[snx][sny][bnx][bny] == 0
) {
arr[snx][sny][bnx][bny] = arr[sNowX][sNowY][snx][sny] + 1;
if (bnx == eX && bny == eY) {
System.out.println(arr[snx][sny][bnx][bny]);
return;
}
queue.offer(new int[]{snx, sny, bnx, bny});
}
}
}
System.out.println(-1);
}
// up right down left
int[] theX = new int[]{-1, 0, 1, 0};
int[] theY = new int[]{0, 1, 0, -1};
}
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; } }
from collections import deque n,m=map(int,input().split()) board=[] s=[] b=[] for i in range(n): tmp=input() board.append(tmp) if not s: sidx=tmp.find('S') if sidx!=-1: s=[i,sidx] if not b: bidx=tmp.find('0') if bidx!=-1: b=[i,bidx] step=-1 q=deque([(s[0],s[1],b[0],b[1],0)]) visit=[[[[False]*m for _ in range(n)]for _ in range(m)]for _ in range(n)] visit[s[0]][s[1]][b[0]][b[1]]=True while q: p0,p1,b0,b1,cnt=q.popleft() if board[b0][b1]=='E': step=cnt break for dx,dy in zip((-1,0,1,0),(0,-1,0,1)): nx,ny=p0+dx,p1+dy if 0<=nx<n and 0<=ny<m and board[nx][ny]!='#': if nx==b0 and ny==b1: nb0,nb1=b0+dx,b1+dy if 0<=nb0<n and 0<=nb1<m and board[nb0][nb1]!='#': if not visit[nx][ny][nb0][nb1]: visit[nx][ny][nb0][nb1]=True q.append((nx,ny,nb0,nb1,cnt+1)) else: if not visit[nx][ny][b0][b1]: visit[nx][ny][b0][b1]=True q.append((nx,ny,b0,b1,cnt+1)) print(step)
#include<bits/stdc++.h> using namespace std; int vis[55][55][55][55]; char gm[55][55]; struct node{ int sx, sy, bx, by, step; }; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(){ int n, m; cin>>n>>m; node s; s.step = 0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>gm[i][j]; if(gm[i][j]=='S'){ s.sx=i;s.sy=j; } if(gm[i][j]=='0'){ s.bx=i;s.by=j; } } } vis[s.sx][s.sy][s.bx][s.by] = 1; queue<node> q; q.push(s); int res = -1; while(!q.empty()&&res==-1){ node cur = q.front(); if(cur.step>1000) break; q.pop(); for(int i=0;i<4&&res==-1;i++){ node next_node; next_node.sx = cur.sx + dx[i]; next_node.sy = cur.sy + dy[i]; // skip when node get out of bound or meet an obstacle if(next_node.sx>=n||next_node.sx<0||next_node.sy>=m||next_node.sy<0||gm[next_node.sx][next_node.sy]=='#') continue; if(next_node.sx==cur.bx&&next_node.sy==cur.by){ next_node.bx = cur.bx + dx[i]; next_node.by = cur.by + dy[i]; if(gm[next_node.bx][next_node.by]=='E') res = cur.step+1; }else{ next_node.bx = cur.bx; next_node.by = cur.by; } if(vis[next_node.sx][next_node.sy][next_node.bx][next_node.by]){ continue; }else{ vis[next_node.sx][next_node.sy][next_node.bx][next_node.by] = 1; next_node.step = cur.step + 1; q.push(next_node); } } } cout<<res; }
function solve(n, m, grid, initState, tx, ty) { const queue = [initState] const visited = new Array(n).fill(0).map(v => { return new Array(m).fill(0).map(v => { return new Array(n).fill(0).map(v => { return new Array(m).fill(0) }) }) }) const isVisited = (state) => { return visited[state[0]][state[1]][state[2]][state[3]] } const setVisited = (state) => { visited[state[0]][state[1]][state[2]][state[3]] = 1 } const getNextState = (state, choice) => { let [x, y, bx, by] = state x += choice[0] y += choice[1] if (x === bx && y === by) { bx += choice[0] by += choice[1] } if (grid[x] === undefined || grid[x][y] === undefined || grid[bx] === undefined || grid[bx][by] === undefined || grid[x][y] === 1 || grid[bx][by] === 1 ) return null return [x, y, bx, by] } const isFinished = (state) => { return state[2] === tx && state[3] === ty } const choices = [[0, 1], [1, 0], [0, -1], [-1, 0]] let count = 1 let depth = 0 while (queue.length !== 0) { const curState = queue.shift() setVisited(curState) for (const choice of choices) { const nextState = getNextState(curState, choice) // 没有以更低的深度或者相同的深度访问过 if (nextState !== null && !isVisited(nextState)) { if (isFinished(nextState)) { // 如果到达完成状态 return depth + 1 } queue.push(nextState) } } count-- if (count === 0) { depth++ count = queue.length } } return -1 } let line = readline() const initState = [0, 0, 0, 0] const [n, m] = line.split(' ').map(v => parseInt(v)) const grid = new Array(n).fill(0).map(v => new Array(m).fill(0)) let tx = 0 let ty = 0 for (let i = 0; i < n; i++) { line = readline() for (let j = 0; j < m; j++) { switch (line[j]) { case '.': break case 'S': initState[0] = i initState[1] = j break case '#': grid[i][j] = 1 break case 'E': tx = i ty = j break case '0': initState[2] = i initState[3] = j } } } console.log(solve(n, m, grid, initState, tx, ty))
#include<iostream> #include<vector> #include<queue> using namespace std; struct node{ int px, py, bx, by; int steps = 0; node() :px(0), py(0), bx(0), by(0){} node(int i, int j, int ii, int jj) :px(i), py(j), bx(ii), by(jj){} }; int solution(vector<vector<char>>& input, node& s,node& e){ const int n = input.size(), m = input[0].size(); vector<vector<vector<vector<int>>>>visited(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(m)))); int x_dirs[4] = {-1,1,0,0 }; int y_dirs[4] = { 0,0,-1,1}; queue<node>q; q.push(s); while (!q.empty()){ node cur = q.front(); q.pop(); if (cur.bx<0 || cur.by<0 || cur.px<0 || cur.py<0 || cur.bx>=n || cur.by>=m || cur.px>=n || cur.py>=m ||input[cur.bx][cur.by]=='#'||input[cur.px][cur.py]=='#' || visited[cur.px][cur.py][cur.bx][cur.by]) continue; if (cur.bx == e.bx && cur.by == e.by) return cur.steps; visited[cur.px][cur.py][cur.bx][cur.by] = 1; for (int i = 0; i < 4; ++i){ int newpx = cur.px, newpy = cur.py; int newbx = cur.bx, newby = cur.by; newpx += x_dirs[i]; newpy += y_dirs[i]; if (cur.bx == newpx && cur.by == newpy){ newbx += x_dirs[i]; newby += y_dirs[i]; } node next(newpx, newpy, newbx, newby); next.steps = cur.steps + 1; q.push(next); } } return -1; } int main(){ //input int n, m; cin >> n >> m; node s, e; vector<vector<char>>input(n, vector<char>(m)); for (int i = 0; i < n; ++i){ for (int j = 0; j < m; ++j){ cin >> input[i][j]; if (input[i][j] == 'S'){ s.px = i; s.py = j; } else if (input[i][j] == '0'){ s.bx = i; s.by = j; } else if (input[i][j] == 'E'){ e.bx = i; e.by = j; } } } cout << solution(input, s, e) << endl; }
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int n, m, x[4] = {1, -1, 0, 0}, y[4] = {0, 0, -1, 1};//四个方向移动,上下左右 char mp[55][55]; bool vis[5050][5050];//记录当前人位置和箱子位置状态是否待访问 //二维坐标结构体 struct node{ int x, y; int toint(){//将二维坐标转化为整型,便于判断是否访问过 return x * 100 + y; } friend bool operator == (node a, node b){ return b.x == a.x && a.y == b.y; } }now, box, target; //记录当前人位置和箱子位置的结构体 struct status{ node now, box; int ans; status(){} status(node _now, node _box, int _ans){ now = _now, box = _box, ans = _ans; } }temp; // 队列存储bfs的状态 queue<status> nxt; int bfs(){ nxt.push(status(now, box, 0));//初始状态 while(!nxt.empty()){ temp = nxt.front(); nxt.pop(); if(temp.box == target){//判断当前箱子位置是否到达终点 return temp.ans; } for(int i = 0; i < 4; ++i){ now = temp.now, box = temp.box; now.x += x[i], now.y += y[i];//移动人的位置 if(now == box){//若人的位置移动后与箱子位置重合则推箱子 box.x += x[i], box.y += y[i]; }//判断人和箱子位置是否同时访问过并合法,确保不越界而且可以到达 if(mp[now.x][now.y] == '.' && mp[box.x][box.y] == '.' && !vis[now.toint()][box.toint()]){ nxt.push(status(now, box, temp.ans + 1)); vis[now.toint()][box.toint()] = true; } } } return -1; } int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i){ scanf("%s", mp[i] + 1); } for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){//将人和箱子起始位置和预期位置记录下来,并改成可到达的位置以便搜索 if(mp[i][j] == 'S'){ now.x = i, now.y = j; mp[i][j] = '.'; } else if(mp[i][j] == '0'){ box.x = i, box.y = j; mp[i][j] = '.'; } else if(mp[i][j] == 'E'){ target.x = i, target.y = j; mp[i][j] = '.'; } } } printf("%d", bfs()); }
#include<bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> v1(n, vector<int>(51, 0)); vector<vector<vector<vector<int>>>> vi(n, vector<vector<vector<int>>>(51, v1)); //int vi[6][51][6][51] = { 0 }; int x, x2, x3, y, y2, y3; vector<vector<char>> v(n, vector<char>(m, '0')); for (int i = 0; i < n; i++) { for (int ii = 0; ii < m; ii++) { cin >> v[i][ii]; if (v[i][ii]== 'S') { x = i; y = ii; } if (v[i][ii]== 'E') { x3 = i; y3 = ii; } if (v[i][ii] == '0') { x2 = i; y2 = ii; } } } queue<vector<int>> q; q.push({ x,y,x2,y2,0 }); while (!q.empty()) { auto qq = q.front(); q.pop(); int x = qq[0], y = qq[1], x2 = qq[2], y2 = qq[3], i = qq[4]; if (x3 == x2 && y3 == y2) { cout << i; return 0; } if (x<0||x2<0||y<0||y2<0||x>=n||y>=m||x2>=n||y2>=m || v[x][y] == '#'|| vi[x2][y2][x][y]==1) continue; vi[x2][y2][x][y] = 1; if ((abs(x - x2) == 1&& y==y2) || (abs(y - y2) == 1 &&x==x2)) { if (x - x2 == 1) { q.push({ x + 1,y,x2,y2,i + 1 }); q.push({ x,y + 1,x2,y2,i + 1 }); q.push({ x - 1,y,x2-1,y2,i + 1 }); q.push({ x ,y - 1,x2,y2,i + 1 }); } else if (x2 - x == 1) { q.push({ x + 1,y,x2+1,y2,i + 1 }); q.push({ x,y + 1,x2,y2,i + 1 }); q.push({ x - 1,y,x2,y2,i + 1 }); q.push({ x ,y - 1,x2,y2,i + 1 }); } else if (y - y2 == 1) { q.push({ x + 1,y,x2,y2,i + 1 }); q.push({ x,y + 1,x2,y2,i + 1 }); q.push({ x - 1,y,x2,y2,i + 1 }); q.push({ x ,y - 1,x2,y2-1,i + 1 }); } else if (y2 - y == 1) { q.push({ x + 1,y,x2,y2,i + 1 }); q.push({ x,y + 1,x2,y2+1,i + 1 }); q.push({ x - 1,y,x2,y2,i + 1 }); q.push({ x ,y - 1,x2,y2,i + 1 }); } } else { q.push({ x + 1,y,x2,y2,i + 1 }); q.push({ x,y+1,x2,y2,i + 1 }); q.push({ x -1,y,x2,y2,i + 1 }); q.push({ x ,y-1,x2,y2,i + 1 }); } } cout << -1; }
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e3+5;
char arr[maxn][maxn];
int n,m;
int sx,sy; //人物起始位置
int bx,by; //箱子起始位置
int ex,ey;
struct node{
int x,y; //当前点坐标
int h,d; //当前箱子坐标
int step;
};
const int maxn_ = 55;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int vis[maxn_][maxn_][maxn_][maxn_]; //1 表示已经走过了
int bfs(int sx,int sy)
{
queue<node> q;
node f; //f表示队首
f.x=sx;
f.y=sy;
f.h=bx;
f.d=by;
f.step=0;
vis[sx][sy][bx][by]=1; //一开始的状态标记为1
q.push(f); //将初始状态入队
int t=1e6+5;
while(!q.empty()) //当队不空时
{
t--;
if(t==0)
{
return -1;
}
f=q.front(); //f接收队首
//cout<<f.x<<" "<<f.y<<endl;
if(f.h==ex && f.d==ey) //如果队首坐标为E点坐标,则返回答案
{
return f.step;
}
q.pop(); //出队操作
int nstep=f.step+1; //下一步的步数为0
int nbx=f.h; //表示盒子的横坐标下一步的盒子假设还没移动
int nby=f.d;
for(int i=0;i<4;++i)
{
int nx=f.x+dir[i][0]; //四个方向的某一个方向坐标
int ny=f.y+dir[i][1];
if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny]=='#') //坐标不合法
{
continue; //如果出界或者遇到墙,则坐标不合法
}
if(f.h==ex && f.d==ey)
{
node temp ;
temp.x=nx;
temp.y=ny;
temp.step=f.step+1;
q.push(temp);
}
/*
if(vis[nx][ny][f.h][f.d]) //状态已经存在了
{
continue;
}
*/
//if(arr[nx][ny]=='0')
if(nx==f.h && ny==f.d)
{
int ox,oy;
ox=nx+dir[i][0];
oy=ny+dir[i][1];
if(ox<0 || ox>=n || oy<0 || oy>=m || arr[ox][oy]=='#' || arr[ox][oy]=='X') //坐标不合法
{
continue;
}
node temp;
temp.x=nx;
temp.y=ny;
temp.h=ox;
temp.d=oy;
temp.step=nstep;
if(!vis[temp.x][temp.y][temp.h][temp.d])
{
q.push(temp);
}
vis[temp.x][temp.y][temp.h][temp.d]=1;
}
else if(arr[nx][ny]=='.' || arr[nx][ny]=='X' || arr[nx][ny]=='E') //如过遇到的是.和X
{
node temp;
temp.x=nx;
temp.y=ny;
temp.h=nbx;
temp.d=nby;
temp.step=nstep;
if(!vis[nx][ny][nbx][nby]) //如果状态没遇到过,则入队
{
q.push(temp);
}
vis[temp.x][temp.y][temp.h][temp.d]=1; //这个状态标记为1
}
}
}
return -1;
}
void judge(int i,int j)
{
int flag1=0,flag2=0,flag3=0,flag4=0;
if(i-1<0)
{
flag1=1;
}else if(arr[i-1][j]=='#')
{
flag1=1;
}
if(j-1<0)
{
flag2=1;
}else if(arr[i][j-1]=='#')
{
flag2=1;
}
if(i+1==n)
{
flag3=1;
}else if(arr[i+1][j]=='#')
{
flag3=1;
}
if(j+1==m)
{
flag4=1;
}else if(arr[i][j+1]=='#')
{
flag4=1;
}
if((flag1 && flag2) || (flag2 && flag3) || (flag3 && flag4) || (flag4 && flag1))
{
arr[i][j]='X';
}
}
int main()
{
memset(vis,0,sizeof(vis));
while(cin>>n>>m)
{
for(int i=0;i<n;++i)
{
scanf("%s",arr+i);
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(arr[i][j]=='S')
{
sx=i;
sy=j;
}
if(arr[i][j]=='0')
{
bx=i;
by=j;
arr[i][j]='.';
}
if(arr[i][j]=='E')
{
ex=i;
ey=j;
}
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(arr[i][j]=='#' || arr[i][j]=='E') continue;
judge(i,j);
}
}
//test map
/*
cout<<endl;
for(int i=0;i<n;++i)
{
cout<<arr[i]<<endl;
}
*/
cout<<bfs(sx,sy)<<endl;
}
return 0;
}
import java.util.*; import java.util.Map.Entry; public class Q40 { public boolean isValid(char[][]board,Position pos) { //pos所表示位置是否合法? int n=board.length,m=board[0].length; int i=pos.boxRow, j=pos.boxColumn; if (!(0<=i&&i<n&&0<=j&&j<m&&board[i][j]!='#')) return false; i=pos.personRow;j=pos.personColumn; if (!(0<=i&&i<n&&0<=j&&j<m&&board[i][j]!='#')) return false; return true; } public int getMinSteps(char[][]board) { int n=board.length,m=board[0].length; int boxRow=-1, boxColumn=-1, personRow=-1, personColumn=-1,targetRow=-1,targetColumn=-1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(board[i][j]=='0') { //箱子起始位置 boxRow=i;boxColumn=j; } else if(board[i][j]=='S') { //人起始位置 personRow=i;personColumn=j; } else if(board[i][j]=='E') { //箱子目标位置 targetRow=i;targetColumn=j; } Position initialPosition=new Position( boxRow, boxColumn, personRow, personColumn); return getMinSteps(board,initialPosition, targetRow, targetColumn); } public int getMinSteps(char[][]board,Position initialPosition,int targetRow,int targetColumn) { int n=board.length,m=board[0].length; HashSet<Position> visited=new HashSet<Position>(); int steps=0; LinkedList<Position>queue=new LinkedList<Position>(); queue.add(initialPosition); visited.add(initialPosition); while(!queue.isEmpty()) { int len=queue.size(); for(int k=0;k<len;k++) { Position temp=queue.poll(); if(temp.boxRow==targetRow&&temp.boxColumn==targetColumn)return steps; Position left=temp.moveLeft(temp); Position right=temp.moveRight(temp); Position up=temp.moveUp(temp); Position down=temp.moveDown(temp); if(isValid(board,left)&&!visited.contains(left)) { visited.add(left); queue.add(left); } if(isValid(board,right)&&!visited.contains(right)) { visited.add(right); queue.add(right); } if(isValid(board,up)&&!visited.contains(up)) { visited.add(up); queue.add(up); } if(isValid(board,down)&&!visited.contains(down)) { visited.add(down); queue.add(down); } } steps++; } return -1; } public static void main(String[] args) { // TODO Auto-generated method stub char[][]board= { {'.','S','#','.','.','E'}, {'.','#','.','0','.','.'}, {'.','.','.','.','.','.'} }; Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m=sc.nextInt(); sc.nextLine(); char[][]board1=new char[n][m]; for(int i=0;i<n;i++) { String temp=sc.nextLine(); for(int j=0;j<m;j++) board1[i][j]=temp.charAt(j); } System.out.print(new Q40().getMinSteps(board1)); } } class Position{ //盒子,人所在的行和列数 public int boxRow, boxColumn, personRow, personColumn; public Position(int boxRow, int boxColumn, int personRow, int personColumn) { super(); this.boxRow = boxRow; this.boxColumn = boxColumn; this.personRow = personRow; this.personColumn = personColumn; } public Position moveLeft(Position pos) { if(pos.boxColumn!=pos.personColumn-1||pos.boxRow!=pos.personRow) //如果箱子不在人左边,人往左移 //否则人和箱子都往左移 return new Position(pos.boxRow,pos.boxColumn,pos.personRow,pos.personColumn-1); else return new Position(pos.boxRow,pos.boxColumn-1,pos.personRow,pos.personColumn-1); } public Position moveRight(Position pos) { if(pos.boxColumn!=pos.personColumn+1||pos.boxRow!=pos.personRow) //如果箱子不在人右边,人往右移 //否则人和箱子都往右移 return new Position(pos.boxRow,pos.boxColumn,pos.personRow,pos.personColumn+1); else return new Position(pos.boxRow,pos.boxColumn+1,pos.personRow,pos.personColumn+1); } public Position moveUp(Position pos) { if(pos.boxColumn!=pos.personColumn||pos.boxRow!=pos.personRow-1) //如果箱子不在人上边,人往上移 //否则人和箱子都往上移 return new Position(pos.boxRow,pos.boxColumn,pos.personRow-1,pos.personColumn); else return new Position(pos.boxRow-1,pos.boxColumn,pos.personRow-1,pos.personColumn); } public Position moveDown(Position pos) { if(pos.boxColumn!=pos.personColumn||pos.boxRow!=pos.personRow+1) //如果箱子不在人下边,人往下移 //否则人和箱子都往下移 return new Position(pos.boxRow,pos.boxColumn,pos.personRow+1,pos.personColumn); else return new Position(pos.boxRow+1,pos.boxColumn,pos.personRow+1,pos.personColumn); } public int hashCode() { // TODO Auto-generated method stub return Objects.hash(boxRow, boxColumn, personRow, personColumn); } public boolean equals(Object obj) { // TODO Auto-generated method stub if(!(obj instanceof Position))return false; Position pos=(Position)obj; return(this.personRow==pos.personRow&&this.personColumn==pos.personColumn &&this.boxRow==pos.boxRow&&this.boxColumn==pos.boxColumn); } public String toString() { return "Position [boxRow=" + boxRow + ", boxColumn=" + boxColumn + ", personRow=" + personRow + ", personColumn=" + personColumn + "]"; } }
import java.util.Scanner; import java.util.ArrayDeque; public class Main { public static void main( String[] args ) { Scanner sc = new Scanner( System.in ); while( sc.hasNext() ) { int m = sc.nextInt(); int n = sc.nextInt(); char[][] map = new char[m][n]; for ( int i = 0; i < m; i++ ) map[i] = sc.next().toCharArray(); Sokoban game = new Sokoban( map ); System.out.println( game.play() ); } } } class Sokoban { private char[][] map; private boolean[][][][] flag; private int tm,tn; private int m, n; private Layout cur; private class Layout { int pm,pn,bm,bn; Layout( int p1, int p2, int p3, int p4 ) { pm = p1; pn = p2; bm = p3; bn = p4; flag[p1][p2][p3][p4] = true; } Layout moveUp() { if( pm - 1 == bm && pn == bn ) { if( bm >= 1 && map[bm-1][bn] != '#' && flag[pm-1][pn][bm-1][bn] == false ) { return new Layout( pm-1, pn, bm-1, bn ); } } else { if( pm >= 1 && map[pm-1][pn] != '#' && flag[pm-1][pn][bm][bn] == false ) { return new Layout( pm-1, pn, bm, bn ); } } return null; } Layout moveDown() { if( pm + 1 == bm && pn == bn ) { if( bm+1 < m && map[bm+1][bn] != '#' && flag[pm+1][pn][bm+1][bn] == false ) { return new Layout( pm+1, pn, bm+1, bn ); } } else { if ( pm+1 < m && map[pm+1][pn] != '#' && flag[pm+1][pn][bm][bn] == false ) { return new Layout( pm+1, pn, bm, bn ); } } return null; } Layout moveLeft() { if( pm == bm && pn - 1 == bn ) { if( bn >= 1 && map[bm][bn-1] != '#' && flag[pm][pn-1][bm][bn-1] == false ) { return new Layout( pm, pn-1, bm, bn-1 ); } } else { if ( pn >= 1 && map[pm][pn-1] != '#' && flag[pm][pn-1][bm][bn] == false ) { return new Layout( pm, pn-1, bm, bn ); } } return null; } Layout moveRight() { if( pm == bm && pn + 1 == bn ) { if( bn+1 < n && map[bm][bn+1] != '#' && flag[pm][pn+1][bm][bn+1] == false ) { return new Layout( pm, pn+1, bm, bn+1 ); } } else { if( pn+1 < n && map[pm][pn+1] != '#' && flag[pm][pn+1][bm][bn] == false ) { return new Layout( pm, pn+1, bm, bn ); } } return null; } } public Sokoban( char[][] map ) { this.map = map; m = map.length; n = map[0].length; flag = new boolean[m][n][m][n]; int p1 = 0, p2 = 0, p3 = 0, p4 = 0; for( int i = 0; i < m; i ++ ) { for( int j = 0; j < n; j ++ ) { if( map[i][j] == 'S' ) { p1 = i; p2 = j; } else if( map[i][j] == '0' ) { p3 = i; p4 = j; } else if( map[i][j] == 'E' ) { tm = i; tn = j; } } } cur = new Layout( p1, p2, p3, p4 ); } public int play() { ArrayDeque<Layout> stack = new ArrayDeque<>(); stack.offer( cur ); Layout tmp; for( int i = 0; !stack.isEmpty(); i ++ ) { int len = stack.size(); for( int j = 0; j < len; j ++ ) { cur = stack.poll(); if( cur.bm == tm && cur.bn == tn ) return i; if( ( tmp = cur.moveUp() ) != null ) stack.offer( tmp ); if( ( tmp = cur.moveDown() ) != null ) stack.offer( tmp ); if( ( tmp = cur.moveLeft() ) != null ) stack.offer( tmp ); if( ( tmp = cur.moveRight() ) != null ) stack.offer( tmp ); } } return -1; } }
/** * 推箱子游戏。 * 思路:直接用BFS从玩家起点开始遍历。注意的是利用buf四维数组存储到当前位置所需的步数。由于利用的是BFS,所以第一次赋给buf的数值一定是最小的步数。 * <br> * <a href=https://interview.nowcoder.com/question/next?pid=8537140&qid=141017&tid=19866373>具体描述</a> * @author LBW */ import java.util.*; public class Main { char[][] space = new char[51][51]; //棋盘二维数组 int[][][][] buf = new int[51][51][51][51]; //buf四维数组,既可以用来存储走过的路径以防重复,又可以直接得到当前局面所需的最小步数。 int n, m; int px, py, bx, by; // px,py: 玩家位置 bx,by:箱子位置 int targetX, targetY; //目标位置 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Main sokoban = new Main(); sokoban.n = scanner.nextInt(); sokoban.m = scanner.nextInt(); for (int i1 = 0; i1 < 51; i1++) { for (int i2 = 0; i2 < 51; i2++) { for (int i3 = 0; i3 < 51; i3++) { for (int i4 = 0; i4 < 51; i4++) { sokoban.buf[i1][i2][i3][i4] = -1; } } } } //Find px,py,bx,by,targetX, targetY for (int i = 0; i < sokoban.n; i++) { String line = scanner.next(); for (int j = 0; j < sokoban.m; j++) { sokoban.space[i][j] = line.charAt(j); if (sokoban.space[i][j] == 'S') { sokoban.px = i; sokoban.py = j; } else if (sokoban.space[i][j] == '0') { sokoban.bx = i; sokoban.by = j; } else if (sokoban.space[i][j] == 'E') { sokoban.targetX = i; sokoban.targetY = j; } } } int result = sokoban.getResult(); System.out.println(result); } // start private int getResult() { if (bx == targetX && by == targetY) { return 0; } // Use BFS to solve the problem. LinkedList<PlayerBox> queue = new LinkedList<>(); queue.add(new PlayerBox(px, py, bx, by, 0)); buf[px][py][bx][by] = 0; while (!queue.isEmpty()) { PlayerBox cur = queue.poll(); //search four directions from current position. PlayerBox next = cur.moveUp(); if (next != null && notInPaths(next)) { if (next.bx == targetX && next.by == targetY) { return next.num; } queue.add(next); buf[next.px][next.py][next.bx][next.by] = next.num; } next = cur.moveDown(); if (next != null && notInPaths(next)) { if (next.bx == targetX && next.by == targetY) { return next.num; } queue.add(next); buf[next.px][next.py][next.bx][next.by] = next.num; } next = cur.moveLeft(); if (next != null && notInPaths(next)) { if (next.bx == targetX && next.by == targetY) { return next.num; } queue.add(next); buf[next.px][next.py][next.bx][next.by] = next.num; } next = cur.moveRight(); if (next != null && notInPaths(next)) { if (next.bx == targetX && next.by == targetY) { return next.num; } queue.add(next); buf[next.px][next.py][next.bx][next.by] = next.num; } } return -1; } // whether the position has been visited private boolean notInPaths(PlayerBox playerBox) { if (buf[playerBox.px][playerBox.py][playerBox.bx][playerBox.by] == -1) return true; else return false; } class PlayerBox { int px, py, bx, by; int num; public PlayerBox(int px, int py, int bx, int by, int num) { this.px = px; this.py = py; this.bx = bx; this.by = by; this.num = num; } public PlayerBox moveUp() { if (bx == px - 1 && by == py) { if (bx - 1 >= 0 && space[bx-1][by] != '#') { return new PlayerBox(px-1, py, bx-1, by, num+1); } } else { if (px - 1 >= 0 && space[px-1][py] != '#') { return new PlayerBox(px-1, py, bx, by, num+1); } } return null; } public PlayerBox moveDown() { if (bx == px + 1 && by == py) { if (bx + 1 < n && space[bx+1][by] != '#') { return new PlayerBox(px+1, py, bx+1, by, num+1); } } else { if (px + 1 < n && space[px+1][py] != '#') { return new PlayerBox(px+1, py, bx, by, num+1); } } return null; } public PlayerBox moveLeft() { if (bx == px && by == py - 1) { if (by - 1 >= 0 && space[bx][by-1] != '#') { return new PlayerBox(px, py-1, bx, by-1, num+1); } } else { if (py - 1 >= 0 && space[px][py-1] != '#') { return new PlayerBox(px, py-1, bx, by, num+1); } } return null; } public PlayerBox moveRight() { if (bx == px && by == py + 1) { if (by + 1 < m && space[bx][by+1] != '#') { return new PlayerBox(px, py+1, bx, by+1, num+1); } } else { if (py + 1 < m && space[px][py+1] != '#') { return new PlayerBox(px, py+1, bx, by, num+1); } } return null; } } }