HDU-4634

2018-03-01

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4634

题目大意

有一个豆腐块想要从初始位置走到出口位置（EXIT），移动方向为上下左右，像象棋里的车，只有走到头才可以改变方向，或者遇到强制转向（L,R,U,D）时转向。如果EXIT被锁住了，那么必须搜集到所有钥匙才可以打开门。当钥匙不全的时候，出口处和普通路没区别。问最少需要多少操作能出去。
这里有一点不太清楚的地方，问多少操作是撞墙转向的数量，遇到强制转换不算转向。

思想

问最短多少步，BFS是显然的。然而直接裸BFS会有两个问题，一个是不好记录取得钥匙的情况，一个是会超时。所以使用状态压缩进行优化。
题目指出，最多7把钥匙，所以我们以二进制位0，1记为没取得钥匙，取得了钥匙。
对于一个方格内的状态，我们可以用四个参数描述。横坐标，纵坐标，当前取得的钥匙和当前面朝的方向。所以用”used[x][y][ss][dir]”记录状态，重复就不再入队了。

代码

HDU-4634

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

int N,M,sx,sy;
int keynum=0;
int key_value[210][210];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char mmap[210][210];
struct Node{
	int x,y;
	int step;
	int key;
};
bool used[210][210][1<<7][4];
int bfs()
{
	queue<Node> q;
	while (!q.empty()) q.pop();
	Node hd;
	hd.x=sx; hd.y=sy; hd.step=0; hd.key=0;
	q.push(hd);
	memset(used,0,sizeof(used));
	while (!q.empty())
	{
		Node now,pre;
		pre=q.front();
		q.pop();
		for (int dir=0;dir<4;dir++)
		{
			int xx=pre.x,yy=pre.y;
			int ss=pre.key;
			int ddir=dir;
			while (1)
			{
				if (mmap[xx][yy] == 'L') ddir=2;
				if (mmap[xx][yy] == 'R') ddir=3;
				if (mmap[xx][yy] == 'U') ddir=0;
				if (mmap[xx][yy] == 'D') ddir=1;

				if (used[xx][yy][ss][ddir]) break; else used[xx][yy][ss][ddir]=true;
				if (mmap[xx][yy] == 'K') ss|=key_value[xx][yy];
				if (mmap[xx][yy] == 'E' && ss == ((1<<keynum)-1)) return pre.step+1;
				if (xx+dx[ddir]>0 && xx+dx[ddir]<=N && yy+dy[ddir]>0 && yy+dy[ddir]<=M)
				{
					if (mmap[xx+dx[ddir]][yy+dy[ddir]] == '#')
					{
						now.x=xx; now.y=yy; now.step=pre.step+1; now.key=ss;
						q.push(now);
						break;
					}
					else
					{
						xx+=dx[ddir];
						yy+=dy[ddir];
					}
				}
				else
					break;
			}
		}
	}
	return -1;
}
int main()
{
	while (scanf("%d%d",&N,&M) == 2)
	{
		keynum=0;
		memset(key_value,0,sizeof(key_value));
		char ch;
		for (int i=1;i<=N;i++)
		{
			scanf("%c",&ch);
			for (int j=1;j<=M;j++)
			{
				scanf("%c",&mmap[i][j]);
				if (mmap[i][j] == 'S')
				{
					sx=i; sy=j;
				}
				else if (mmap[i][j] == 'K')
				{
					key_value[i][j]=1<<keynum;
					keynum++;
				}
			}
		}
		printf("%d\n",bfs());
	}
	return 0;
}

后记

坚持。