题目描述

一群殖民者登陆了一座未知岛屿，寻找适合定居的地点。然而岛上已有原住民，双方为生存展开竞争。殖民者需通过寻找食物维持生存（目前尚未掌握农耕技术），一旦食物耗尽就必须迁移。若不同群体相遇，由于资源稀缺，他们将战斗至死。你的任务是模拟$N$轮后各群体的存活状态和位置。

岛屿环境

• 岛屿是 $A \times B$ 的矩形网格，每个格子为以下类型：
  • W：水域（不可进入）
  • M：山脉（不可进入）
  • .：普通平原
  • w：生长小麦的平原（食物来源）
  • Z：群体初始位置（Z后接数字表示群体编号和人口数）

群体行为规则（每轮按编号从小到大行动）

1. 攻击：若相邻（上下左右）有其他群体，优先攻击（按北→东→南→西顺序选择目标）。
2. 进食：若相邻有小麦，按顺时针方向消耗小麦（每单位小麦养活1人），剩余人口继续寻找相邻小麦。
3. 移动：若无食物可吃，按以下规则移动：
   • 计算每个方向的“探索积分”（访问次数越少优先级越高，上一移动方向积分加倍）。
   • 选择积分最低的方向移动（北→东→南→西的优先级处理平局）。

人口变化规则

• 进食后：人口增加 $\lceil 0.33 \times \text{进食人数} \rceil$，未进食者死亡 $\lceil 0.05 \times \text{未进食人数} \rceil$。
• 攻击后：攻击方造成 $\lceil 0.5 \times \text{人口} \rceil$ 点伤害，自身死亡 $\lceil 0.1 \times \text{人口} \rceil$。
• 移动后：死亡 $\lceil 0.1 \times \text{人口} \rceil$。

输入格式

• START N：N为模拟轮数。
• 地图：A行B列的网格，每个格子用“标识符 数字”表示（如 2 060 表示编号2的群体初始人口60）。
• END：数据结束标记。

输出格式

按群体编号升序输出：

GroupID Size (X,Y) YearDied（若已死亡）

示例输入 1

START 5
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
W 000 W 000 . 000 . 000 2 060 . 000 w 345 W 000
W 000 . 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 1 140 . 000 . 000 0 050 . 000 . 000 W 000
W 000 W 000 . 000 M 000 M 000 . 000 . 000 W 000
W 000 W 000 w 200 M 000 M 000 . 000 3 025 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 w 115 w 115 . 000 . 000 W 000
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
END

示例输出 1

0 0 (4,2) 2
1 57 (4,1)
2 43 (5,1)
3 31 (6,2)

题目来源

South Central USA 2001