🥇 Taiwan

TOI 臺灣國際資訊奧林匹亞競賽 Taiwan Olympiad in Informatics 📅 2024/06/17~2024/06/21 🧒 新手組 T3

吸血鬼 (Vampire)

📝 问题叙述

数百年前，猎人赢得对抗吸血鬼的战争，将所有吸血鬼都封印起来。然而，基于某种未知的力量，有几只吸血鬼突破了封印。猎人首领在接收到消息后，也立刻部署了猎人，准备再度消灭它们。

王国领土是由 H × W（H 列 W 行）的正方形土地所构成，每块土地有一个村庄。每一天的午夜到太阳升起前，吸血鬼会向四个斜角的村庄感染，扩大吸血鬼的势力；要是吸血鬼发现目标村庄已经是猎人的势力，就不会再去感染那个村庄。太阳升起后，猎人的势力会向东南西北四个方位的村庄扩张，并消灭势力范围内的吸血鬼。

请你编写一个程序，给定第 0 天的势力分布状态，求得第 K 天后的势力分布。

📥 输入格式

• 第一行输入三个整数 H（3 ≤ H ≤ 100）、W（3 ≤ W ≤ 100）和 K（1 ≤ K ≤ 10），分别表示王国领土的长和宽，以及要预测的天数。
• 接下来有 H 行输入，每行含有 W 个整数，表示村庄的在第 0 天的状态；
  • -1 表示吸血鬼势力；
  • 0 表示尚无势力介入；
  • 1 表示猎人势力。

📤 输出格式

• 输出 H 行，每行含有 W 个整数，表示经过第 K 天后的王国状态。同一列的两个整数间以一个空格间隔。

📚 示例 1

输入：

5 5 2
0 0 0 0 0
0 0 -1 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0

输出：

0 -1 0 -1 0
-1 0 -1 1 -1
0 -1 1 1 1
-1 1 1 1 1
0 0 1 1 1

📚 示例 2

输入：

3 3 1
0 0 0
0 -1 1
0 0 0

输出：

-1 0 1
0 1 1
-1 0 1

💡 评分说明

此题目测试数据分为两组，每组测试有多笔测试数据，需答对该组所有测试数据才能获得该组分数。各组详细限制如下：

1. ​**第一组 (60 分)**​：K = 1。
2. ​**第二组 (40 分)**​：无特殊限制。

💡 思路说明

1. ​吸血鬼的感染过程​：
   • 每天，吸血鬼会向四个对角线的村庄传播其势力，若该村庄已有猎人势力，则不会再被感染。
2. ​猎人的扩张过程​：
   • 白天，猎人会向四个方位（东南西北）扩展其势力，消灭势力范围内的吸血鬼。
3. ​模拟多天的扩张过程​：
   • 根据输入的天数 K，模拟 K 天的吸血鬼和猎人势力变化。
4. ​输出状态​：
   • 输出 K 天后的王国状态。

🎯 解题步骤

1. ​初始化状态​：根据输入初始化王国的每个村庄的状态（吸血鬼、猎人或空白）。
2. ​模拟一天的变化​：
   • 吸血鬼先感染四个对角线的村庄。
   • 然后，猎人扩展到四个方位的村庄。
3. ​重复步骤​：根据给定的天数 K 重复以上步骤。
4. ​输出结果​：输出经过 K 天后的王国状态。