首页 > 搜索 > DFS搜索 > HDU 4634-Swipe Bo-BFS-[解题报告]HOJ
2015
09-17

HDU 4634-Swipe Bo-BFS-[解题报告]HOJ

Swipe Bo

问题描述 :

“Swipe Bo” is a puzzle game that requires foresight and skill.
The main character of this game is a square blue tofu called Bo. We can swipe up / down / left / right to move Bo up / down / left / right. Bo always moves in a straight line and nothing can stop it except a wall. You need to help Bo find the way out.
The picture A shows that we needs three steps to swipe Bo to the exit (swipe up, swipe left, swipe down). In a similar way, we need only two steps to make Bo disappear from the world (swipe left, swipe up)!
Who's Aunt Zhang

Look at the picture B. The exit is locked, so we have to swipe Bo to get all the keys to unlock the exit. When Bo get all the keys, the exit will unlock automatically .The exit is considered inexistent if locked. And you may notice that there are some turning signs, Bo will make a turn as soon as it meets a
Who's Aunt Zhang

turning signs. For example, if we swipe Bo up, it will go along the purple line.
Now, your task is to write a program to calculate the minimum number of moves needed for us to swipe Bo to the exit.

输入:

The input contains multiple cases, no more than 40.
The first line of each test case contains two integers N and M (1≤N, M≤200), which denote the sizes of the map. The next N lines give the map’s layout, with each line containing M characters. A character is one of the following: ‘#’: represents the wall; ‘S’ represents the start point of the Bo; ‘E’ represents the exit; ‘.’ represents an empty block; ‘K’ represents the key, and there are no more than 7 keys in the map; ‘L’,'U’,'D’,'R’ represents the turning sign with the direction of left, up, down, right.

输出:

The input contains multiple cases, no more than 40.
The first line of each test case contains two integers N and M (1≤N, M≤200), which denote the sizes of the map. The next N lines give the map’s layout, with each line containing M characters. A character is one of the following: ‘#’: represents the wall; ‘S’ represents the start point of the Bo; ‘E’ represents the exit; ‘.’ represents an empty block; ‘K’ represents the key, and there are no more than 7 keys in the map; ‘L’,'U’,'D’,'R’ represents the turning sign with the direction of left, up, down, right.

样例输入:

5 6
######
#....#
.E...#
..S.##
.#####
5 6
######
#....#
.....#
SEK.##
.#####
5 6
######
#....#
....K#
SEK.##
.#####
5 6
######
#....#
D...E#
S...L#
.#####

样例输出:

3
2
7
-1

跟以前做冰壶那个题有点类似,题目大意是说每次你可以从上下左右走,只有当碰到墙壁的时候才停下,另外所给地图中存在各种自动转向点,当走到的时候立即进行转向。还有就是若图中存在钥匙,那么要得到所有的钥匙以后出口才能打开,才能从出口出去。现在让你求出从起点到终点至少需要多少步

思路:

1、状态压缩,由于题目所述图中钥匙最多只有7把,所以可以由数字的位表示,这样最多只需要对每个状态多开128大小的数组

2、进行搜索的时候注意对自动转向点的处理,我用的是DFS搜索,但被RE了几次,然后想到其可能形成循环转向,也就是转圈,从而进入死循环,这个地方需要特殊处理下。

3、去重的时候用除了用坐标表示以外,还要用数字表示当前位置时所含有的钥匙,注意如果出界的话这个状态是不需要记录的。

4、剩下的就是编码了~

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=201;
const int maxm=130;
struct node
{
    int x;
    int y;
    int key;
    int ans;
}q[maxn*maxn*maxm];
char map[maxn][maxn];
int n,m,k,sx,sy,desx,desy,pre,last,keyx[8],keyy[8],cur,movex[4]={1,-1,0,0},movey[4]={0,0,-1,1};
bool vis[maxn][maxn][maxm];
bool isborder(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m)
	return true;
    return false;
}
int Move(int x,int y,int key,int ans,int pos)
{
    while(1)
    {
	x+=movex[pos];
	y+=movey[pos];
	if(isborder(x,y))
	    return 0;
	if(map[x][y]=='E'&&key==k)
	    return ans;
	if(map[x][y]=='K')
	{
	    for(int i=0;i<cur;i++)
		if(keyx[i]==x&&keyy[i]==y)
		{
		    key|=(1<<i);
		    break;
		}
	    continue;
	}
	if(map[x][y]=='L')
	{
	    if(!vis[x][y][key])
	    {
		vis[x][y][key]=1;
		int val=Move(x,y,key,ans,2);
		vis[x][y][key]=0;
		return val;
	    }
	    return 0;
	}
	if(map[x][y]=='R')
	{
	    if(!vis[x][y][key])
	    {
		vis[x][y][key]=1;
		int val=Move(x,y,key,ans,3);
		vis[x][y][key]=0;
		return val;
	    }
	    return 0; 
	}
	if(map[x][y]=='D')
	{
	    if(!vis[x][y][key])
	    {
		vis[x][y][key]=1;
		int val=Move(x,y,key,ans,0);
		vis[x][y][key]=0;
		return val;
	    }
	    return 0;
	}
	if(map[x][y]=='U')
	{
	    if(!vis[x][y][key])
	    {
		vis[x][y][key]=1;
		int val=Move(x,y,key,ans,1);
		vis[x][y][key]=0;
		return val;
	    }
	    return 0;
	}
	if(map[x][y]=='#')
	{
	    x-=movex[pos];
	    y-=movey[pos];
	    break;
	}
    }
    if(!vis[x][y][key])
    {
	vis[x][y][key]=1;
	node ita;
	ita.x=x;
	ita.y=y;
	ita.key=key;
	ita.ans=ans;
	q[last++]=ita;
    }
    return 0;
}
int BFS()
{
    node st;
    st.x=sx;
    st.y=sy;
    st.key=0;
    st.ans=0;
    memset(vis,0,sizeof(vis));
    pre=0,last=1;
    q[pre]=st;
    vis[st.x][st.y][st.key]=1;
    while(pre<last)
    {
	node now=q[pre++];
	for(int i=0;i<4;i++)
	{
	    int ans=Move(now.x,now.y,now.key,now.ans+1,i);
	    if(ans)
		return ans;
	}
    }
    return -1;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
	cur=0;
	for(int i=0;i<n;i++)
	    scanf("%s",map[i]);
	for(int i=0;i<n;i++)
	    for(int j=0;j<m;j++)
	    {
		if(map[i][j]=='S')
		{
		    sx=i;
		    sy=j;
		}
		else if(map[i][j]=='E')
		{
		    desx=i;
		    desy=j;
		}
		else if(map[i][j]=='K')
		{
		    keyx[cur]=i;
		    keyy[cur++]=j;
		}
	    }
	k=(1<<cur)-1;
	printf("%d\n",BFS());
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/z309241990/article/details/9992351


, ,