POJ1475『推箱子』

题目大意:相信大家都很熟悉推箱子游戏。从前有个地图,像这样——

//输入数据中’#’表示墙,’.’表示空地,S表示你,B表示盒子,T表示盒子终点

现在要将盒子推到终点,求一种移动方案使箱子移动次数最少的前提下人移动的次数最少。

方案中”ESWN”表示箱子的推动,”ewsn”表示人的移动。

题解:

在题目中要求箱子&人都tm要走,而且还不是同步的。

但是——人要推箱子。也就是箱子的移动必须靠人来推动。

∴当箱子向某个方向移动时,人的位置是确定的。

问题转化为——箱子向终点跑,人跑来跑去推箱子。

即——

1、使箱子“想要”往k方向移动一步

2、人走到箱子的k方向的反方向(如果走得到的话)一推,啪

3、箱子移动,人移动。

至此容易想到双重bfs——外层箱子,内层人。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#define MAXN 50
using namespace std;
int n, m;
char map[MAXN][MAXN];
int mx, my, bx, by, tx, ty; 
int fx[4] = {-1, 0, 1, 0};
int fy[4] = {0, -1, 0, 1};
char c[4] = {'n', 'w', 's', 'e'};
//大坑点,如果不按照如上方向顺序扩展的话会WA
int fman[MAXN][MAXN][4], fbox[MAXN][MAXN][4];
bool vis[MAXN][MAXN][4];
bool vis2[MAXN][MAXN];
struct State
{
	int x, y;
	int sx, sy;
	string ans;
};
struct Dot
{
	int x;
	int y;
	string ans;
};
State t(int x, int y, int sx, int sy, string ans)
{
	State tmp;
	tmp.x = x;
	tmp.y = y;
	tmp.sx = sx;
	tmp.sy = sy;
	tmp.ans = ans;
	return tmp;
}
Dot z(int x, int y, string ans)
{
	Dot tmp;
	tmp.x = x;
	tmp.y = y;
	tmp.ans = ans;
	return tmp;
}
char up(char ch)
{
	return (ch - 'a'+ 'A');
}
string bfsman(int stx, int sty, int enx, int eny, int bxx, int bxy)
{
	Dot v;
	int x, y;
	string ans;
	if(stx < 0 || stx > n || sty < 0 || sty > m || map[stx][sty] == '#') return "-1";
	memset(vis2, 0, sizeof(vis2));
	vis2[bxx][bxy] = 1;
	vis2[stx][sty] = 1;
	queue <Dot> qq;
	qq.push(z(stx, sty, ""));
	while(!qq.empty())
	{
		v = qq.front();
		qq.pop();
		x = v.x;y = v.y;
		ans = v.ans;
		if(x == enx && y == eny) return ans;
//关于最短:不难发现后入队的ans字母数量一定多于前入队的,因此第一次取出最终态便是最优。
		for(int i = 0;i < 4;i++)
		{
			int dx = x + fx[i];
			int dy = y + fy[i];
			if(dx > 0 && dx <= n && dy > 0 && dy <= m && !vis2[dx][dy] && map[dx][dy] != '#')
			{
				qq.push(z(dx, dy, ans + c[i]));
				vis2[dx][dy] = 1;
			}
		}
	}
	return "-1";
}
string bfsbox()
{
	memset(vis, 0, sizeof(vis));
	int boxx, boxy, manx, many, dir, bxed, byed;
	queue <State> q;
	q.push(t(bx, by, mx, my, ""));
	while(!q.empty())
	{
		State u = q.front();
		q.pop();
		boxx = u.x;boxy = u.y;
		manx = u.sx; many = u.sy;
		if(boxx == tx && boxy == ty) return u.ans;//最先取出最优,理由同上
		for(int i = 0;i < 4;i++)
		{
			bxed = boxx + fx[i];
			byed = boxy + fy[i];
			if(bxed > 0 && bxed <= n && byed > 0 && byed <= m && !vis[bxed][byed][i] && map[bxed][byed] != '#')
			{
				string man = bfsman(manx, many, boxx - fx[i], boxy - fy[i], boxx, boxy);
				if(man != "-1")
				{
					q.push(t(bxed, byed, boxx, boxy, u.ans + man + up(c[i])));
					vis[bxed][byed][i] = 1;
				}
			}
		}
	}
	return "Impossible.";
}
int main()
{
	int Case = 0;
	while(~scanf("%d%d", &n, &m) && (n || m))
	{
		for(int i = 1;i <= n;i++)
		{
			scanf("%s", map[i]+1);
			for(int j = 1;j <= m;j++)
			{
				if(map[i][j] == 'S') {mx = i; my = j;}
				if(map[i][j] == 'T') {tx = i; ty = j;}
				if(map[i][j] == 'B') {bx = i; by = j;}
			}
		}
		printf("Maze #%d\n", ++Case);
		cout<<bfsbox();
		printf("\n\n");//俩回车哦
	}
}

 

点赞
  1. lhaoyuan_renjie说道:

    哇!兹磁兹磁

  2. lhaoyuan_renjie说道:

    :huaji20:

  3. 哥666666说道:

    大佬大佬牛逼牛逼(话说这个网站怎么搞的?)

    1. Akaresol说道:

      码代码丫。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00