#P2339. Rock, Scissors, Paper

Rock, Scissors, Paper

题目描述

巴特的妹妹丽莎在一个二维网格上创造了一种新文明。初始时,每个网格位置可能被三种生命形式之一占据:石头(Rocks)、剪刀(Scissors)或布(Papers)。每天,占据水平或垂直相邻网格位置的不同生命形式会展开战斗。在每场战斗中,石头总是击败剪刀,剪刀总是击败布,布总是击败石头。一天结束时,胜者会将其领土扩展到包括失败者的网格位置,失败者则会撤离该位置。

你的任务是确定经过nn天后,每个生命形式所占据的领土情况。

输入格式

输入的第一行包含一个整数tt,表示测试用例的数量。
每个测试用例以三个不超过100100的整数开始:rrcc,分别表示网格的行数和列数,以及nn(天数)。
接下来的rr行,每行包含cc个字符,表示网格的初始状态。每个字符为R、S或P,分别代表石头、剪刀和布。

输出格式

对于每个测试用例,输出nn天后的网格状态。
连续的测试用例输出之间需留一个空行。

样例输入输出

输入数据 1

2  
3 3 1  
RRR  
RSR  
RRR  
3 4 2  
RSPR  
SPRS  
PRSP  

输出数据 1

RRR  
RRR  
RRR  

RRRS  
RRSP  
RSPR  

关键规则

  • 战斗规则
    • R(石头)击败 S(剪刀),即 R > S;
    • S(剪刀)击败 P(布),即 S > P;
    • P(布)击败 R(石头),即 P > R。
  • 领土扩张:每天结束时,若相邻位置存在不同生命形式且发生战斗,胜者会占据失败者的位置,失败者撤离。
  • 相邻方向:仅考虑水平(左右)和垂直(上下)的相邻位置,即每个位置最多与4个相邻位置互动。