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;
}

最后

以上就是安详眼睛为你收集整理的hdu1242（Rescue）深搜的全部内容，希望文章能够帮你解决hdu1242（Rescue）深搜所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。