编程题1-推箱子(字节跳动2018校招)_推箱子编程题

题目描述

有一个推箱子的游戏, 一开始的情况如下图:

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置，其中 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

算法分析

典型的迷宫搜索问题，求最短时间，我们首先想到BFS。 
和典型的迷宫搜索问题不同的是，本题中的搜索可以分为两个阶段。 
第一阶段：游戏玩家从起始位置“S”走到箱子的位置（箱子的上、下、左、右）。 
第二阶段：游戏玩家把箱子从“0”位置推到“E”位置。 
在第一阶段中，和普通的BFS一样。在第二阶段中，玩家要和箱子一起移动。

提交代码：

#include<iostream>
#include<vector>
#include<string>
#include<memory.h>
#include<map>
#include<queue>
 
using namespace std;
struct Node {
	int x, y, b_x, b_y, step;
	Node(int x, int y, int b_x, int b_y, int step) :
		x(x), y(y), b_x(b_x), b_y(b_y), step(step) {};
};
 
int n, m;
vector<string> path;
// xy bxby 推着箱子走
int visited[50][50][50][50];
const vector<pair<int, int>> direc = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };
 
bool valid(int x, int y)
{
	if (x < 0 || x >= n || y < 0 || y >= m || path[x][y] == '#') return false;
	return true;
}
 
int bfs(int start_x, int start_y, int box_x, int box_y)
{
	queue<Node> que;
	que.push(Node(start_x, start_y, box_x, box_y, 0));
	visited[start_x][start_y][box_x][box_y] = 1;
	while (!que.empty()) {
		Node node = que.front();
		que.pop();
		int bx = node.b_x;
		int by = node.b_y;
		int step = node.step;
		for (int i = 0; i < 4; ++i) {
			int x = node.x + direc[i].first;
			int y = node.y + direc[i].second;
			// 箱子被同方向推动的位置
			int next_x = bx + direc[i].first;
			int next_y = by + direc[i].second;
 
			if (!valid(x, y)) continue;
			// 走到箱子旁边
			if ((x != bx || y != by) && visited[x][y][bx][by] == 0) {
				visited[x][y][bx][by] = 1;
				que.push(Node(x, y, bx, by, step + 1));
				// 推箱子
			}
			else if (x == bx && y == by && valid(next_x, next_y) && visited[x][y][next_x][next_y] == 0) {
				visited[x][y][next_x][next_y] = 1;
				if (path[next_x][next_y] == 'E')
					return step+1;
				que.push(Node(x, y, next_x, next_y, step + 1));
			}
		}
	}
 
	return -1;
}
 
int main()
{
	memset(visited, 0, sizeof(visited));
	cin >> n >> m;
	path = vector<string>(n, string(""));
	for (int i = 0; i < n; ++i) cin >> path[i];
	int start_x, start_y, box_x, box_y;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (path[i][j] == 'S') {
				start_x = i, start_y = j;
			}
			else if (path[i][j] == '0') {
				box_x = i, box_y = j;
			}
		}
	}
	cout << bfs(start_x, start_y, box_x, box_y) << endl;
	return 0;
}