U450313 Among The Pigs - Normal
题目背景
9名猪接到任务，要去火星基地完成任务，不幸的是，有6只不怀好意的猪进入了飞船，有的想去火星基地搞破坏（坏猪），~~有的只是想在火星上搞传销（幸存猪）~~，搞破坏的猪要把别的猪干掉，赶紧把它们揪出来，否则······**$\color{red} {后果很严重}$**
题目描述
### 游戏目的
- 好猪 / GP：努力使BP和NP无法完成胜利条件,完成所有任务或干掉（投出或刀掉）场上所有带刀职业（不包括自己人）
- 坏猪 / BP：可以搞破坏，干掉所有GP和NP，直到场上不存在带刀职业（不包括自己人）且 $坏猪剩余人数>=场上剩余人数 \div 2$
- 中立猪 / NP：各自为战，完成自己的胜利条件
### 人员构成
- 总共： $15$ 只猪
- 好猪： $9$ 只，占 $60\%$
- 坏猪： $3$ 只，占 $20\%$
- 中立猪： $3$ 只，占 $20\%$
### 游戏职业
- 前置~~知识~~
+ CD cold down 表示技能冷却
+ 刀猪 把猪干掉，留下s体
- 好猪
+ **普通猪 / PT** 普普通通，没有技能，只会完成任务的劳模
+ **警长猪 / JZ** 可以干掉别的猪，如果干到好猪的话，会自己暴毙，另一只好猪不会（ $CD:20s$ ）
+ **预言猪 / YY** 对一只猪使用技能后，可以看到它的阵营，只能查验2次（ $CD:45s$ ）
+ **医生猪 / YS** 对一只死亡的猪使用技能后10秒，猪会复活，技能限用两次（ $CD:45s$ ）
+ **赌徒猪 / DT** 在会议期间（后面会介绍）可以与一只猪打赌，如果对方是好猪且不带刀则赌徒猪暴毙，否则对方被干掉（ $CD:仅限会议期间$ ）
+ **正义猪 / ZY** 有一次刀猪权限，且刀人不会暴毙（ $CD:10s$ ）
+ **无敌猪 / WD** 可以免受一次死亡（包括投票）
+ **诱饵 / YR** 被刀后立即强迫凶手报告
+ **传送猪 / CS** 使用技能后把所有猪传送到自己位置（ $CD:30s$ ）
+ **迷你小猪 / MN** 新手保护，出生时 $0$ 岁，每隔 $30s$ 成长1岁（会议不算时间，会议结束后**不重置**），成年前不可受到伤害，无法被票出
+ **殉道猪 / XD** 用自己的生命复活别的猪，复活的猪性质与医生复活的相同，不留下自己的s体（ $CD：10s$ ）
+ **守望猪 / SW** 技能扩大视野范围 $5s$ ，范围见后（ $CD：35s$ ）
+ **猪长 / ZZ** 有极高的威望，一票当 $3$ 票，包括弃票
+ **禁票猪 / JP** 取消一只猪本轮的投票权
+ **老猪 / LZ** 技能使用期间**对其**使用任意技能的猪死，技能持续 $5s$ （ $CD：35s$ ）
- 坏猪
+ **普通坏猪 / PH** 只能刀猪（ $CD:25s$ ）
+ **摄魂猪 / SH** 可以刀猪，当自己死掉后可以在下一轮（一轮以会议结束为时间节点）附身在队友刀掉的s体上，附身后的摄魂猪只能再刀一次人，但是没有 $CD$ （ 原刀猪$CD:25s$ ）
+ **头目 / TM** 只能刀猪，但技能 $CD$ 减少至 $20s$ （ $CD:20s$ ）
+ **赏金猎猪 / SJ** 如果现在刀掉的猪是目前存活的敌方阵营的猪中编号最小的， $CD$ 降为 $3$ 秒，否则增加 $CD$ 至 $35s$ ，会议后重置（初始刀猪 $CD：25s$ ）
+ **猪营长 / ZP** 可以向左/右开炮（激光炮，别抬杠），炮的距离无限，宽度为7格，撞到/本来就在弹道上的猪死（不分敌我），持续5秒，3秒前摇，前摇期间猪营长无法移动，包括无敌/幸存（见后），无法刀猪（ $CD：50s$ ）
+ **猪帝 / ZD** 技能召见最近的猪，不限距离，最近定义：欧氏距离最小（欧式距离=$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$）（刀猪与召见$CD$相同：$25s$）
+ **坏迷你小 / HM** 同迷你小,多了个刀猪技能，成年前 $CD：30s$，成年后 $20s$
+ **清理猪 / QL** 可以清理队友刀猪留下的s体，当队友全部死亡时才可解锁刀猪技能，清理技能会被替换掉（清理 $CD$ 与刀猪 $CD$ 一致）（ $CD：30s$）
- 中立猪
+ **JOKEP / JO**（JOKE R->P）被投票出局即可获胜（胜利条件在所有阵营之上，也就是只要被票出就会胜利，不考虑坏猪/纵火猪（见后）胜利条件）
+ **幸存猪 / XC** 可以免受一次死亡（不包括投票），游戏结束时任在场则与获胜阵营共同胜利
+ **墙头猪 / QT** 刀人后加入坏猪，但是会被通报墙头草（刀人后无刀），刀人前是好猪阵营，跟随胜利（$CD:15s$）
+ **饕餮 / TT** 吃s体，吃够3个获胜，吃掉的s体会消失，就像清理一样（ $CD：20s$ ）
+ **纵火猪 / ZH** 给猪打标记，当场上每一个猪都有标记时获胜（标记 $CD：15s$ ）
+ **野猪 / YZ** 获胜条件与坏猪相似，干掉所有人胜利，但是可以招募一个跟班，跟班不带刀，且失去原来身份，当野猪死后，跟班成为下一任野猪，可以继续招募其他猪，但跟班死后原野猪不可再招募（招募&刀猪 $CD：25s$ ）
- 注：**好猪**的身份可能相同，但一局一个职业最多有两个猪扮演
### 游戏流程
1. 开局，特殊地，第一轮坏猪刀猪 CD=10s（刀掉第一个猪的时候降回25(20)s）
2.过程，好猪做任务，坏猪刀猪，中立其他
3. 会议，会议有两个触发条件，当一个猪选择“通报发现s体”时触发，或当一只猪拉紧急会议时触发
4. 讨论，特别地，好猪只说真话，坏猪只说假话，中立会有时说真话，有时说假话，说什么将在后面介绍
5. 投票，每只猪会对当前状况投票给它认为最有可能是的敌方阵营的猪，得票最高者淘汰，如果没有则弃票，弃票人数超过在场最高票数时跳过，在场任何一猪（或弃票选项）的票数相等则平票，不会有人被淘汰
6. 重复步骤2~5
### 行动（非会议时）准则
- 前置~~知识~~$\times 2$
+ “坏猪列表” 猪会列出一个列表，当遇到一只猪很可疑的状况时，除特殊指出的，否则给它加一票，投票/决策时会选择票数最高的猪，平票则选择编号更小的，当一只猪死亡时，票数降到负无穷
+ “好猪列表” 同坏猪队列，与之相反
+ 当众，**目标**在地图中上下左右2格内有其他猪，如图，P表示目标，“*”中有其他猪（不包括自己）就算：
+ 落单，与当众相反
```
*
* * *
* * P * *
* * *
*
```
- 好猪
+ **普通猪** 按任务单上的顺序走向任务点完成任务（停留三秒完成任务）（猪不聪明，但还是会走最短路线的）
+ **警长猪 $CD$ 好时会**当众**干掉自己“坏猪列表”中的票数最高的三只猪（不会刻意去追，随缘，遇到就刀），刀成功了立即报告，不管医生/殉道，两个事件在同一秒完成，殉道来不及，没有目标时同普通猪
+ **预言猪** 同普通猪，$CD$ 好时会查验与第一个 $CD$ 好后遇到的人
+ **医生猪** 一定在找到一只s体后等待 $CD$ 好后复活该猪
+ **赌徒猪** 同普通猪
+ **正义猪** 同警长猪
+ **无敌猪** 同普通猪，盾被刀掉后无敌猪是不知道的
+ **传送猪** 同普通猪，有技能就放
+ **迷你小** 同普通猪
+ **殉道猪** 同普通猪，有尸体时放技能
+ **守望猪** 有技能就放
+ **猪长** 同普通猪
+ **禁票猪** 同普通猪
+ **老猪** 同普通猪，在**看到**自己“坏猪列表”中的票数最高的三只猪时放技能，零票及以下不算，如果对方死了立即报告，同警长猪，来不及殉道
+ **所有好猪**：除非有医生猪（有殉道也不），否则看到s体后一定报告，有医生时会等待医生 $30s$ 医生未到时将会报告，并且通报所有猪 “医生死亡” 的消息，以后不再等待医生
- 坏猪
+ **普通坏猪** $CD$ 好后会在一只猪**落单**时刀掉它
+ **摄魂猪** 同普通坏猪，但第 $3$ 刀的时候不一定要等猪落单（除非它原先已经死过了，现在是摄魂之身）
+ **头目** 同普通坏猪
+ **赏金猎猪** 同普通坏猪
+ **猪营长** 有技能就放，先会测算向哪边放覆盖的格子跟多，相同则向左
+ **猪帝** 同普通猪，召见和刀猪一起放
+ **坏迷你** 同普通坏猪
+ **清理猪** 队友死完后同普通坏猪，其余时间会跟在队友身后，跟随原则： $头目>坏迷你（成年）>赏金猎猪>猪帝>普通坏猪>坏迷你（未成年）>摄魂猪>猪营长$
+ **所有坏猪** 都会对s体视而不见
- 中立猪
+ **JOKEP** 有医生时立即报告，否则站在s体上装坏猪
+ **幸存猪** 同无敌猪，但是当盾被刀掉后知道，并将这个结果记录下来，会议时告诉大家，幸存猪默认好猪报告方式
+ **墙头猪** 当场上坏猪数量是场上人数的 $\frac {1} {3}$ 时，出刀（出刀方式不限，有猪就刀，反正都会通报），否则不出刀，出刀前好猪报告方式，出刀后坏猪报告方式
+ **饕餮** 能放技能就放
+ **纵火** 能放技能就放
+ **野猪** 优先招募，接下来同坏猪
+ **跟班** 跟随野猪
- 所有猪在没有可做的任务时有额外行走方式（与完成任务类似）
### 紧急会议
- 触发条件：在一只猪走到会议桌**上**时可以选择是否开启（同任务，但不需要等 $3$ 秒）
- 猪会走最短路径
- 预言猪在查验到非好猪时会发起
- 守望看到猪架炮/刀猪时选择按会议更近还是通报发现s体更近
- 幸存猪盾被刀时会发起
- 其他好猪/幸存猪看到架炮时
- 按紧急会议的路上遇到s体报告（越过医生检测）
### 会议规则
- 好猪
+ 共性 猪是会记忆的，它会记住最后一个遇到的猪 $10$ 秒，如果记住期间内遇到了s体，它会认为该猪是坏猪， **但不报告这一现象，而是仅仅使它编号前三位猪和后三位猪知晓**，**看到炮和看到s体性质相同**
+ **预言猪** 查验出的好猪会通报并使所有猪在坏猪列表中减它一票（允许负数），查验出的坏猪会加入 “坏猪列表” 并通报，加3票
+ **被医生复活的猪** 猪在被刀后会记下刀它的猪（提示：一只猪可能被刀两次，又被复活两次）并通报，**猪们会首先投出它**，即放在队列顶部而不是底部
+ **赌徒猪** 它会与 “坏猪队列” 中第一只猪的猪打赌
+ **诱饵** 在第一次会议时通报自己身份，以后报告其s体者会被在坏猪列表中**加两票**
+ **禁票猪** 禁用一轮坏猪列表中第一位猪的投票
- 坏猪
+ **共性** 同好猪，但它们会投当前报告的猪，因为好猪有可能在队列中的猪不同
- 中立猪
+ **JOKEP** 总是投自己
+ **幸存猪** 当盾被刀掉后会告诉大家谁干的，大家会先投出它，**优先级仅在“墙头猪”之下**
+ **墙头猪** 同好猪/坏猪（出刀后），特殊地，当它被通报后，会先被投出，**优先级仅在“被医生复活的猪”之下**
+ **共性** 未提到的同好猪
### 其他规则
- 技能施展（刀猪，招募等）距离，如图
```
*
* P *
*
```
- 互刀，当两猪处于敌对状态且要刀对方时，两猪互刀，都死掉，特殊的，警长猪与正义猪互刀时，两猪的技能都会被消耗，只有警长死掉，体现在答案中时（在后面输出格式）仅体现警长紫砂
- 视野，如图，当在视野范围内看到s体时走过去，看到目标时追击
```
*
* * *
* * P * *
* * *
*
```
- **守望猪**技能视野
```
*
* * *
* * * * *
* * * * * * *
* * * * * * * * *
* * * * * P * * * * *
* * * * * * * * *
* * * * * * *
* * * * *
* * *
*
```
- **营长猪**的弹道
```
* * * *
* * * * *
* * * * * *
P * * * * * * * ······
* * * * * *
* * * * *
* * * *
```
- 速度，猪的速度 $1格/s$
- 允许两只猪在同一位置
- 允许“隔墙有眼”
- 猪必须要**站在**任务点上才能完成任务
- 判定从1号开始，例如传送猪把所有猪传送到二营长的弹道上一锅端了，从1号开始噶，一个一个判定，数据保证不会无解
输入格式
1. 15行，表示1~15号猪，格式：编号（一定按顺序，只是为了方便辨认） 阵营 身份 '{' 任务（仅好猪有） '}'，'|'， '{' 附加任务（用于保证猪的移动，所有猪都有，做完所有任务后循环“做”这些任务）'}' 结束符‘;’（半角）
eg: `01 GP PT { 01 } | { 01 }`
2. 两个整数，$n,m$，表示地图的行数、列数（1个全角符号算1格，两个半角符号算1格）
3. 地图，如图，随机生成，字符都是**全角符号**（半角数字不是地图的一部分，是任务点，替换成‘＋’即可）：
- “１２３４５６７８９０ＪＱＫＡＳ”**依次**表示[1,15]号玩家出生点（会议后和开局点位）
- “＃”表示墙，数据保证地图最外围是墙，过道的宽度为 $1$
- “＋”允许行走
- “Ｍ”会议桌
4. 一个整数，$k$ ，表示任务点数量
5. 接下来 $k$ 行，每行三个整数，表示任务点的编号（不加前导0，不一定按顺序写出，不一定连续）及横纵坐标 $x,y$ （包括墙，例如下图的七号点就是 $（5,2）$ ，最左上角是 $（1,1）$ ）
```
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃０＋＋07＋＃Ｍ＃01＋＋＋＋＋＋＋１＃
＃＋＃＋＃＃＃＋＃＋＃＃＃＃＃＋＃＃＃
＃９＃＋＃Ｊ＋＋＋＋＋02＋＋＃＋＋２＃
＃＋＃＃＃＋＃＃＃＃＃＃＃＋＃＋＃＃＃
＃８＋06＋Ｑ＋＋＋＋＃＋＋＋＃＋＋３＃
＃＃＃＋＃＋＃＋＃＋＃＃＃03＃＃＃＃＃
＃７＋＋＃＋＃＋＃Ｓ＃＋＃＋＋＋＋４＃
＃＋＃05＃Ｋ＃＃＃＃＃＋＃＃＃＃＃＃＃
＃６＃＋＃＋＋＋＋Ａ＋＋＋04＋＋＋５＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
```
输出格式
15行，包含1~15号猪的游戏数据
格式：**猪的编号（不足两位用 $0$ 补齐），猪的胜负，猪的生存状态，猪的游戏过程**
- 01 DEFEAT DEAD KILLEDBY 14 REVIVEDBY 3 KILLEDBY VOTE
- 上述表示1号猪输了并且噶了，游戏过程中被14刀掉，被3号复活，最后被投出
具体地，
1. 胜负分别用 **“VICTORY”和“DEFEAT”** 表示
2. 生存状态 存活/死亡 分别用 **“SURVIVAL”和“DEAD”** 表示
3. 游戏过程就两个， **“KILLEDBY”（被···杀）和“REVIVEDBY”（被···复活）** ，在后面加猪的编号或“VOTE”（投票），特殊地，幸存猪和无敌猪的盾被刀掉后不需要体现，摄魂猪附身属于自己复活自己，警长猪、赌徒猪紫砂是 “KILLEDBY 自己编号”
说明/提示
### 样例解释
还原样例如图
```
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃０ 10 ＃Ｍ＃ 01 １＃
＃09＃ ＃＃＃ ＃ ＃＃＃＃＃ ＃＃＃
＃９＃ ＃Ｊ 11 ＃02 ２＃
＃08＃＃＃＋＃＃＃＃＃＃＃ ＃ ＃＃＃
＃８ 07 Ｑ 15＃ ＃03 ３＃
＃＃＃ ＃ ＃ ＃ ＃＃＃ ＃＃＃＃＃
＃７ ＃ ＃12＃Ｓ＃ ＃04 ４＃
＃ ＃06＃Ｋ＃＃＃＃＃ ＃＃＃＃＃＃＃
＃６＃ ＃ 13 Ａ 14 05 ５＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
```
看得出来，所有坏猪都无法刀猪（路线原因），所以最终好猪做完所有任务胜利
### 数据范围
| Task ID | n | m | k | pts |
| :-----------: | :-----------: | :-----------: |:-----------: |:-----------: |
| 1 | $100 \le n \le 200$ | $100 \le m \le 200$ | $10 \le k \100$ | 10 |
| 2 | $200 \le n \le 300$ | $200 \le m \le 300$ | $10 \le k \100$ | 20 |
| 3 | $300 \le n \le 400$ | $300 \le m \le 400$ | $10 \le k \100$ | 30 |
| 4 | $400 \le n \le 500$ | $400 \le m \le 500$ | $10 \le k \100$ | 40 |
对于 $100\%$ 的数据，$10 \le n,m \le 500$，$10 \le k \le 100$
### **$\color{red}{最后的最后,}$[下一题网址](https://www.luogu.com.cn/problem/U459312)**