TIOJ 1584 Doraemon and Dorayaki [sort]

poao899    1452K    46MS    G++     1.07K     2009-11-19 11:26:57                         .


Manhattan Distance.[曼哈頓距離(?]


然後注意如果剛好0吃到也不行

(是要保留一點力氣吃嗎orz)


//***************************

#include<stdio.h>
#include<algorithm>
#define abs(x) ((x)>0?(x):-(x))
struct node{
	int x,y;
	int dis;
	int dist(node &b){
		return abs(x-b.x)+abs(y-b.y);
	}
	bool operator<(const node &b)const{
		return dis<b.dis;
	}
	void set(int i,int j){
		x=i;y=j;
	}
}dora,yaki[1000010];
int h,w,hp,g,yakiCnt,c,t;
main(){
	scanf("%d",&t);
	while(t--){
	yakiCnt=0;
	scanf("%d%d%d%d\n",&h,&w,&hp,&g);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			c=getchar();
			switch(c){
				case 'D':
					dora.set(i,j);
				break;
				case 'e':
					yaki[yakiCnt++].set(i,j);
				break;
			}
		}
		getchar();
	}
	for(int i=0;i<yakiCnt;i++)
		yaki[i].dis=dora.dist(yaki[i]);

	std::sort(yaki,yaki+yakiCnt);
	int i;
	for(i=0;i<yakiCnt;i++){
		if(hp-yaki[i].dis>0){
			hp-=yaki[i].dis;
			hp+=g;
			if(hp-yaki[i].dis>0)
				hp-=yaki[i].dis;
			else{
				//printf("%d\n",i);
				break;
			}
		}
		else{
			//printf("%d\n",i);
			break;
		}
	}
	printf("%d\n",i);
}
}