武林
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4347 Accepted Submission(s): 1225
Problem Description
在一个有12行12列的方形的武林世界里，少林、武当和峨嵋三派的弟子们在为独霸武林而互相厮杀。武林世界的第一行的一列格子的坐标是(1, 1)，第一行第二列坐标是(1, 2)……右下角的坐标为(12, 12)。如图：
少林派弟子总是在同一列回不停地行走。先往下走，走到头不能再走时就往上走，再到头则又往下走……比如，(1, 1) -> (2, 1) -> (3, 1)。
武当派弟子总是在同一行来回不停地行走。先往右走，走到头不能再走时就往左走，再到头则又往右走……比如，(2, 1) -> (2, 2) -> (2, 3)。
峨嵋派弟子总是在右下-左上方向来回不停走，先往右下方走，走到头不能再走时就往左上方走，再到头则又往右下方走……比如，(1, 1) -> (2, 2) -> (3, 3)。峨嵋弟子如果位于(1,12)或(12,1)，那当然只能永远不动。每次走动，每个弟子必须，而且只能移动一个格子。
每名弟子有内力、武艺、和生命力三种属性。这三种属性的取值范围都是大于等于0，小于等于100。
少林派弟子总是在同一列回不停地行走。先往下走，走到头不能再走时就往上走，再到头则又往下走……比如，(1, 1) -> (2, 1) -> (3, 1)。
武当派弟子总是在同一行来回不停地行走。先往右走，走到头不能再走时就往左走，再到头则又往右走……比如，(2, 1) -> (2, 2) -> (2, 3)。
峨嵋派弟子总是在右下-左上方向来回不停走，先往右下方走，走到头不能再走时就往左上方走，再到头则又往右下方走……比如，(1, 1) -> (2, 2) -> (3, 3)。峨嵋弟子如果位于(1,12)或(12,1)，那当然只能永远不动。每次走动，每个弟子必须，而且只能移动一个格子。
每名弟子有内力、武艺、和生命力三种属性。这三种属性的取值范围都是大于等于0，小于等于100。
当有两名不同门派的弟子进入同一个格子时，一定会发生一次战斗，而且也只有在这种情况下，才会发生战斗。（同派弟子之间当然不会自相残杀；一个格子里三派弟子都有时，大家都会因为害怕别人渔翁得利而不敢出手；而多名同门派弟子也不会联手对付敌人，因为这有悖于武林中崇尚的单打独斗精神，会被人耻笑）一次战斗的结果将可能导致参战双方生命力发生变化，计算方法为：
战后生命力 = 战前生命力 - 对方攻击力
而不同门派的弟子攻击力计算方法不同：
少林派攻击力 = (0.5 * 内力 + 0.5 * 武艺) * (战前生命力 + 10) / 100
武当派攻击力 = (0.8 * 内力 + 0.2 * 武艺) * (战前生命力 + 10) / 100
峨嵋派攻击力 = (0.2 * 内力 + 0.8 * 武艺) * (战前生命力 + 10) / 100
对攻击力的计算过程为浮点运算，最终结果去掉小数点后部分取整，使得攻击力总是整数。
一次战斗结束后，生命力变为小于或等于0的弟子，被视为“战死”，会从武林中消失。
两名不同门派的弟子相遇时，只发生一次战斗。
初始状态下，不存在生命值小于或等于0的弟子，而且一个格子里有可能同时有多个弟子。一系列战斗从初始状态就可能爆发，全部战斗结束后，仍然活着的弟子才开始一齐走到下一个格子。总之，不停地战斗－行走－战斗－行走……所有弟子都需等战斗结束后，才一齐走到下一个格子。你需要做的是，从一个初始状态，算出经过N步（N < 1000）后的状态。所有的弟子先进行完全部战斗（当然也可能没有任何战斗发生），然后再一齐走到下一个格子，这称为一步。所有弟子总数不会超过1000。
战后生命力 = 战前生命力 - 对方攻击力
而不同门派的弟子攻击力计算方法不同：
少林派攻击力 = (0.5 * 内力 + 0.5 * 武艺) * (战前生命力 + 10) / 100
武当派攻击力 = (0.8 * 内力 + 0.2 * 武艺) * (战前生命力 + 10) / 100
峨嵋派攻击力 = (0.2 * 内力 + 0.8 * 武艺) * (战前生命力 + 10) / 100
对攻击力的计算过程为浮点运算，最终结果去掉小数点后部分取整，使得攻击力总是整数。
一次战斗结束后，生命力变为小于或等于0的弟子，被视为“战死”，会从武林中消失。
两名不同门派的弟子相遇时，只发生一次战斗。
初始状态下，不存在生命值小于或等于0的弟子，而且一个格子里有可能同时有多个弟子。一系列战斗从初始状态就可能爆发，全部战斗结束后，仍然活着的弟子才开始一齐走到下一个格子。总之，不停地战斗－行走－战斗－行走……所有弟子都需等战斗结束后，才一齐走到下一个格子。你需要做的是，从一个初始状态，算出经过N步（N < 1000）后的状态。所有的弟子先进行完全部战斗（当然也可能没有任何战斗发生），然后再一齐走到下一个格子，这称为一步。所有弟子总数不会超过1000。
Input
第一行是测试数据的组数，随后是各组测试数据。每组数据第一行是行走步数 N。
接下来的若干行，每行描述一名弟子的位置及其各项参数。描述弟子时，格式为“弟子代号 行号 列号 内力 武艺 生命力”。弟子代号就是一个字母：
‘S’ 代表少林派弟子
‘W’ 代表武当派弟子
‘E’ 代表峨嵋派弟子
比如：
W 10 2 10 3 10
表示第10行第2列有一名武当派弟子，他的内力是 10，武艺是3，生命力是10。
每组测试数据以一个结束标志行结尾。结束标志行只含有一个字符’0’。
接下来的若干行，每行描述一名弟子的位置及其各项参数。描述弟子时，格式为“弟子代号 行号 列号 内力 武艺 生命力”。弟子代号就是一个字母：
‘S’ 代表少林派弟子
‘W’ 代表武当派弟子
‘E’ 代表峨嵋派弟子
比如：
W 10 2 10 3 10
表示第10行第2列有一名武当派弟子，他的内力是 10，武艺是3，生命力是10。
每组测试数据以一个结束标志行结尾。结束标志行只含有一个字符’0’。
Output
针对每组测试数据，您的输出应该是4行，前3行每行是用空格分隔的两个整数，前一个是某派弟子总数，后一个是本派所有弟子生命力之和。规定第1行代表少林派，第2行代表武当派，第3行代表峨嵋派。第4行是 “***”表示结束。
Sample Input
2
1
S 1 2 20 20 20
W 2 1 20 20 20
0
2
S 1 2 20 20 20
W 2 1 20 20 20
E 12 12 20 20 100
0
Sample Output
1 20
1 20
0 0
***
1 14
1 14
1 100
***
武林这道题就是使用模拟法写的，从开始到结束，一步步模拟上面所述的情况
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; struct node_t { int x, y; // position int nl; // 内力 int wy; // 武艺 int hp; // 生命 bool hasFight; int d; // direction: 0:up, down:1 node_t() {} node_t(int xx, int yy, int nnl, int wwy, int hhp, bool h=false, int dd=0) { x = xx; y = yy; nl = nnl; wy = wwy; hp = hhp; hasFight=h; d = dd; } } ; int map[15][15]; vector<node_t> vnodes[3]; // 0:少林, 1:武当, 2:峨眉 int dir[3][2][2] = { { {1, 0}, {-1, 0} }, { {0, 1}, {-1, 0} }, { {1, 1}, {-1, -1} } }; int nn[3];//用来保存每个门派的人数 int t, n; void init() {//初始化地图还有每个门派 memset(map, 0, sizeof(map)); for (int i=0; i<3; ++i) { vnodes[i].clear(); nn[i] = 0; } } inline bool check(int x, int y) {//如果一个函数很简单，而又要被多次调用，就可以声明为inline，内联函数，可以减少运行时间 return x>0 && x<13 && y>0 && y<13; } int getDPS(int i, int j) { double tmp; if (i == 0) { tmp = (0.5*vnodes[i][j].nl + 0.5*vnodes[i][j].wy) * (vnodes[i][j].hp + 10.) / 100.0;//少林派攻击力 } else if (i == 1) { tmp = (0.8*vnodes[i][j].nl + 0.2*vnodes[i][j].wy) * (vnodes[i][j].hp + 10.) / 100.0;//武当派攻击力 } else { tmp = (0.2*vnodes[i][j].nl + 0.8*vnodes[i][j].wy) * (vnodes[i][j].hp + 10.) / 100.0;//峨眉派攻击力 } return (int) tmp; } void fight() { int dps0, dps1;//比武的两个人 int i, j, k, p; int ii, jj, kk; int x, y; for (i=0; i<3; ++i) { for (j=0; j<nn[i]; ++j) { if (vnodes[i][j].hp>0 && map[vnodes[i][j].x][vnodes[i][j].y]==2 && !vnodes[i][j].hasFight) { x = vnodes[i][j].x; y = vnodes[i][j].y; vnodes[i][j].hasFight = true;//把遍历到的其中一人设为已经打架了 for (ii=0; ii<3; ++ii) {//当一个格子里有两个人，如果是同派的就不打架 if (ii == i) continue; for (jj=0; jj<nn[ii]; ++jj) {//如果不是同派的就遍历这个派的所有人，直到找到那个可以打架的格子，把另一个人的打架标示标志为true，表示他们已经打过了，不用再打了 if (vnodes[ii][jj].hp>0 && vnodes[ii][jj].x==x && vnodes[ii][jj].y==y) { dps0 = getDPS(i, j); dps1 = getDPS(ii, jj); vnodes[i][j].hp -= dps1; vnodes[ii][jj].hp -= dps0; vnodes[ii][jj].hasFight = true; } } } } } } } void move() { int i, j, k; int x, y; for (i=0; i<3; ++i) {// 遍历三个门派 for (j=0; j<nn[i]; ++j) {//遍历每个门派的每个人 vnodes[i][j].hasFight = false;//因为要移动，先把每个人的打架指数改为没有打架 x = vnodes[i][j].x; y = vnodes[i][j].y; --map[x][y];//把那个人在地图上的位置上的人数减去一； k = vnodes[i][j].d;//把现在那个人的方向给k if (i == 0) {//对于少林派，如果到了地图最边缘就改变横着走的方向 if (x == 12) k = 1; if (x == 1) k = 0; if (k) { --x; } else { ++x; } } else if (i == 1) {//对于武当派，如果到了地图最边缘就改变纵着走的方向 if (y == 12) k = 1; if (y == 1) k = 0; if (k) { --y; } else { ++y; } } else {//如果是峨眉派，到了地图边角就改变横着和纵着走的方向，如果刚好在犄角旮旯就不用移动 if (x==12 || y==12) k = 1; if (x==1 || y==1) k = 0; if ((x==1&&y==12) || (x==12 && y==1)); else { if (k) { --x; --y; } else { ++x; ++y; } } } vnodes[i][j].d = k;//把已经移动过的方向，纵坐标和横坐标给本派弟子,地图上的人数加一 vnodes[i][j].x = x; vnodes[i][j].y = y; ++map[x][y]; } } } int main() { int i, j, k, tmp; int x, y, nl, wy, hp; char cmd[1];//注意这里必须用字符串接受输入，虽然不知道什么原因，改成%c就错了 scanf("%d", &t); while (t--) { init(); scanf("%d", &n); while (scanf("%s", cmd)!=EOF && (cmd[0]!='0')) { scanf("%d %d %d %d %d", &x, &y, &nl, &wy, &hp); if (cmd[0] == 'S') j = 0; if (cmd[0] == 'W') j = 1; if (cmd[0] == 'E') j = 2; ++map[x][y]; vnodes[j].push_back(node_t(x,y,nl,wy,hp)); ++nn[j]; } while (n--) { fight(); move(); } for (i=0; i<3; ++i) { k = 0; n = 0; for (j=0; j<nn[i]; ++j) { if (vnodes[i][j].hp > 0) {//把武力值大于0的本派的人数和武力值都加起来 k += vnodes[i][j].hp; ++n; } } printf("%d %d ", n, k); } puts("***"); } return 0; }