ACM试题(2)

{

cout<<\ó\ return; } } }

flag=true;

for (k=0;k

if (num[k]%2==1) {

flag=false; break; } }

if (flag) {

len_max=j-i; f=i+1; r=j;

}

} }

cout<

死亡迷宫

背景

很久以前，迷宫里住着一个恶魔。一天，我们伟大的英雄Andy无意中踏入了这个迷宫。不幸的是，他被困在这个迷宫当中了。恶魔在迷宫中召唤出了许多怪物，想要阻止Andy逃脱。在迷宫中，Andy遇到一个一位巫师。他给了Andy迷宫的地图，并告诉他迷宫的入口很快会关闭。Andy必须以非常快的速度到达入口，并且有足够的力气推开挡在入口的岩石。于是，Andy带着地图一路向着出口走去?? 问题

给出Andy和各怪物的能量, 攻击力, 防御力，和迷宫的地图，请你计算一下 能量/耗时 的最大值。

当Andy走到有怪物的地方时，Andy会先进行攻击，然后怪物攻击，然后Andy??当一方的能量小于等于0时攻击停止，并且小于等于0的一方死亡。攻击时，每次对方损耗的能量为己方的攻击力减去对方的防御力。

当Andy走到标有‘A’,‘B’,‘C’的地方时，Andy的相应属性会得到增加。

对应关系如下：

[A] 能量 + P [B] 攻击力 + Q [C] 防御力 + R

如果耗时超过100，那么门将永远也打不开了，我们的Andy也就永远的困在了这个暗无天日的迷宫之中?? 输入

标准输入包含多组数据。

每组数据的第一行有六个整数W (1 <= W <= 20), H (1 <= H <= 20), P (1 <= P <= 10), Q (1<= Q <= 10), R (1 <= R <= 10), M (0 <= M <= 5). 迷宫是由一个W*H的矩形区域构成。M表示怪物的数量。Andy每个单位时间可以移动到相邻的4个格中，当然，必须得保证目标格在矩形区域中。默认的起始时间是0。与怪物战斗不会花费额外的时间。

其后H行每行严格包含W个字符。用如下的各字符表示这个迷宫的地图：

[#]表示一堵墙（Andy是不会穿墙术的）

[.] Marks an empty space, into which you can move.表示一块空地。 [S]表示Andy的初始位置。 [E]表示迷宫的入口。 [0]表示各怪物。

[A]表示属性增加地点。（使用次数仅限于一次）

其后一行有三个整数，表示Andy的能量，攻击力，和防御力。

其后M行，每行有四个整数，表示怪物的编号，和这个怪物的各属性。 输出

对于每组输入数据，输出 能量/耗时 的最大值，并保留4位小数。如果Andy不能到达出

口，输出“impossible”。数据之间无空行。 样例输入

6 17 7 5 4 3 ################# ##E......#......# #A#....#.0.##.#B# #1###########2### #.S............C# ################# 100 59 10 0 23 48 0 1 65 41 0 2 20 27 0 样例输出 3.7037

答案:

#include #include #include using namespace std;

#define MAX_MAP_SIZE 20 #define MAX_MON_SIZE 5 #define Time 100 int W,H,P,Q,R,M;

char map[MAX_MAP_SIZE][MAX_MAP_SIZE];

typedef struct Andy {

int p; int q; int r; } *pAndy;

typedef struct Monster {

int id; int p; int q; int r;

}*pMonster;

typedef struct Node {

int x; int y; }* pNode;

Andy andy;

Monster mons[MAX_MON_SIZE]; char keywords[4+MAX_MON_SIZE];

int shortestPath(pNode path,int len_path,char des,char * revs,int len_rev,int time); float escape(char *revs,int len_revs,int time,Andy andy); bool getPosition(char ch,pNode p); void main() {

ifstream in(\

in>>W>>H>>P>>Q>>R>>M; int i;

for (i=0;i

in>>map[i];

//cout<

in>>andy.p>>andy.q>>andy.r;

for(i=0;i

in>>mons[i].id; in>>mons[i].p; in>>mons[i].q; in>>mons[i].r; }

in.close();

keywords[0]='E'; keywords[1]='A'; keywords[2]='B'; keywords[3]='C'; for (i=0;i

keywords[4+i]='0'+i; }

/*Node path[MAX_MAP_SIZE*MAX_MAP_SIZE]; path[0].x=4; path[0].y=2; int len_path=1; char des='E';

char revs[10]=\ int len_rev=8; int time=100;

cout<

char revs[10]=\ int len_revs=2; int time=100;

cout<

/*char revs[10]=\ int len_revs=5;

Node path[MAX_MAP_SIZE*MAX_MAP_SIZE]; int len_path=1;

int time=100;

for(int j=1;j<4;j++) {

getPosition(revs[j],path);

cout<

}*/ }

int shortestPath(pNode path,int len_path,char des,char * revs,int len_rev,int time) {

if (len_path==0) {

return -1; }

pNode p=path+len_path-1; //µ±Ç°½Úµã

if (map[p->x][p->y]==des) //ÕÒµ½Ä¿±ê {

return len_path-1; }

if (time<1) //ûÓÐʱ

¼ä¼ÌÐøÑ°ÕÒ {

return -1; }

int i,j,k;

for (i=0;i

if (map[p->x][p->y]==revs[i]) {

Node nodes[4]={{p->x,p->y-1},{p->x,p->y+1},{p->x-1,p->y},{p->x+1,p->y}}; int min=W*H; int temp; int bid=-1; bool flag;

for (j=0;j<4;j++) {

flag=true;

for (k=0;k

if(path[k].x==nodes[j].x&&path[k].y==nodes[j].y) {

flag=false; break; } }

if (flag) {

path[len_path]=nodes[j];

temp=shortestPath(path,len_path+1,des,revs,len_rev,time-1); if (temp>0&&temp

min=temp; bid=i; } } }

return bid==-1? -1:min; } }

return -1; }