【HDU3345】War Chess(搜索)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 12 日

War chess is hh's favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
In the map:
'Y' is your current position (there is one and only one Y in the given map).
'.' is a normal grid. It costs you 1 MV to enter in this gird.
'T' is a tree. It costs you 2 MV to enter in this gird.
'R' is a river. It costs you 3 MV to enter in this gird.
'#' is an obstacle. You can never enter in this gird.
'E's are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with 'E', you will lose all your MV. Here “adjacent” means two grids share a common edge.
'P's are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on '.' . so ,it also costs you 1 MV to enter this grid.
题意:给出一个点,并且这个点能向上下左右一定的步数,给出一组减少步数的规则,求所有能到达的点做出标记*。
题解:一个简单的搜索就可以了,各种方法能过。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
char mp[110][110];
const int MAX=110,QMAX=MAX*MAX;
int Q[QMAX][2];
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int r,c;
int Len[MAX][MAX];
int InQ[MAX][MAX];
bool hasE(int tr,int tc)
{
	for(int i=0;i!=4;i++)
	{
		int cr=tr+dir[i][0],cc=tc+dir[i][1];
		if(cr>=0 && cc>=0 && cr<r && cc<c)
		{
			if(mp[cr][cc]=='E') return true;
		}
	}
	return false;
}
int main()
{
	//freopen("in.txt","r",stdin);
	int t,m,yr,yc;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&r,&c,&m);
		for(int i=0;i!=r;i++)
		{
			for(int j=0;j!=c;j++)
			{
				cin>>mp[i][j];
				if(mp[i][j]=='Y')
				{
					yr=i;yc=j;
				}
			}
		}
		CLR(Len,0x3f);
		int head=0,tail=0;
		Q[tail][0]=yr;Q[tail++][1]=yc;
		Len[yr][yc]=0;
		while(head!=tail)
		{
			int cr=Q[head][0],cc=Q[head][1];
			if(++head>=QMAX) head=0;
			for(int i=0;i!=4;i++)
			{
				int tr=cr+dir[i][0],tc=cc+dir[i][1];
				if(tr>=0 && tc>=0 && tr<r && tc<c)
				{
					int dis=0;
					switch(mp[tr][tc])
					{
					case '.':
					case 'P':
					case 'Y':dis=1;break;
					case 'T':dis=2;break;
					case 'R':dis=3;break;
					default:dis=0x3f3f3f3f;break;
					}
					if(Len[cr][cc]+dis<Len[tr][tc])
					{
						Len[tr][tc]=Len[cr][cc]+dis;
						if(!InQ[tr][tc] && !hasE(tr,tc)) 
						{
							Q[tail][0]=tr;Q[tail][1]=tc;
							if(++tail>QMAX) tail=0;
							InQ[tr][tc]=true;
						}
					}

				}

			}
			InQ[cr][cc]=false;
		}
		for(int i=0;i!=r;i++)
			{
				for(int j=0;j!=c;j++)
				{
					if(Len[i][j]<=m && mp[i][j]!='P' &&mp[i][j]!='Y') putchar('*');
					else putchar(mp[i][j]);
				}
				puts("");
			}
			puts("");
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日