hdu1242（Rescue）深搜

134 阅读 0 评论 89 点赞

我是靠谱客的博主安详眼睛，这篇文章主要介绍hdu1242（Rescue）深搜，现在分享给大家，希望可以做个参考。

题意：天使被困在监狱，他的朋友们想见他，监狱的地形复杂，包括路(用点标示),墙(用#标示)，天使的位置（用a标示），他的朋友(用r标示),监狱里还有守卫(用x标示),他的朋友只能向左右上下四个方向走，走以不花一单位时间，若碰上守卫，消灭守卫需要额外花费一单位时间。问最少多长时间天使能见到他的朋友。

题目要注意的是公主的朋友可能不止一个，所以应该以公主的位置为起点进行深搜（刚开始我就没注意到，害我一直超时）

复制代码

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 201
char map[MAX][MAX];
int m,n,mincount,flag;
bool visited[MAX][MAX];

void dfs(int x,int y,int count)
{
	if(count>=mincount)//剪枝
	return ;
	if(map[x][y]=='r')
	{
		flag=1;
		if(count<mincount)
		mincount=count;
		return ;
	}
	if(x>=n||x<0||y<0||y>=m||visited[x][y]==true||map[x][y]=='#')
	return ;
	if(map[x][y]=='x')
	{
		visited[x][y]=true;
		dfs(x+1,y,count+2);
		dfs(x-1,y,count+2);
		dfs(x,y-1,count+2);
		dfs(x,y+1,count+2);
		visited[x][y]=false;
	}
	else
	{
		visited[x][y]=true;
		dfs(x+1,y,count+1);
		dfs(x-1,y,count+1);
		dfs(x,y-1,count+1);
		dfs(x,y+1,count+1);
		visited[x][y]=false;
	}
	
	
}

int main()
{
	int x,y;
	while(cin>>n>>m)
	{
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='a')//起点为angle的位置
			{
				x=i;y=j;
			}
		}
		memset(visited,false,sizeof(visited));
		flag=0;
		mincount=100000;
		dfs(x,y,0);
		if(flag)
		cout<<mincount<<endl;
		else
		cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 201
char map[MAX][MAX];
int m,n,mincount,flag;
bool visited[MAX][MAX];

void dfs(int x,int y,int count)
{
	if(count>=mincount)//剪枝
	return ;
	if(map[x][y]=='r')
	{
		flag=1;
		if(count<mincount)
		mincount=count;
		return ;
	}
	if(x>=n||x<0||y<0||y>=m||visited[x][y]==true||map[x][y]=='#')
	return ;
	if(map[x][y]=='x')
	{
		visited[x][y]=true;
		dfs(x+1,y,count+2);
		dfs(x-1,y,count+2);
		dfs(x,y-1,count+2);
		dfs(x,y+1,count+2);
		visited[x][y]=false;
	}
	else
	{
		visited[x][y]=true;
		dfs(x+1,y,count+1);
		dfs(x-1,y,count+1);
		dfs(x,y-1,count+1);
		dfs(x,y+1,count+1);
		visited[x][y]=false;
	}
	
	
}

int main()
{
	int x,y;
	while(cin>>n>>m)
	{
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='a')//起点为angle的位置
			{
				x=i;y=j;
			}
		}
		memset(visited,false,sizeof(visited));
		flag=0;
		mincount=100000;
		dfs(x,y,0);
		if(flag)
		cout<<mincount<<endl;
		else
		cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
	}
	return 0;
}