#PQJ165x524. QOJ 165_524
QOJ 165_524
扫地机器人 (robot) 扫地机器人 (robot) 【问题描述】 九条可怜是一个懒懒的女孩子。因为懒得扫地,九条可怜买了一架扫地机器 人。 九条可怜的家可以抽象成一个𝑛 × 𝑚的网格,坐标从(1,1)到(𝑛, 𝑚)。每一天 晚上,可怜都会在(1,1)处启动扫地机器人。在启动了之后,扫地机器人会按照设 定好的路径开始行动,当再一次回到(1,1)后便会停止。 因为一些技术原因,扫地机器人只能向右(列编号加一)或者向下(行编号 加一)走。为了让扫地机器人能够顺利的回到(1,1),可怜在家中安装了一些通道, 使得: • 如果机器人目前在(𝑖, 𝑚),那么向右走一步会到(𝑖, 1)。 • 如果机器人目前在(𝑛, 𝑖),那么向下走一步回到(1, 𝑖)。 可怜希望,在启动了机器人之后,在机器人回到(1,1)前,它可以经过每一个 格子恰好一次。这样既可以把家里给打扫干净,也不会花太多时间。经过简单的 计算,可怜很快就得到了所有不同的方案(两个方案是不同的当且仅当他们经过 格子的顺序不同)。于是可怜把所有的方案都输入到了扫地机器人里。 这一天可怜购置了一些新的家具,放好家具之后,家里便多了一些扫地机器 人无法通过的障碍,于是在所有之前准备的方案中,扫地机器人都会撞上某一个 障碍而停止工作。 对于一个方案𝑆,可怜定义𝑓(𝑆)为在这个方案中,扫地机器人在撞上障碍之 前,经过了多少个格子。现在可怜想要对之前所有不同的方案,计算𝑓(𝑆)的和。 【输入格式】 输入文件包含多组测试数据。输入第一行一个整数𝑇表示测试数据的数量。 对于每组测试数据,第一行输入两个整数 𝑛, 𝑚,表示可怜家的大小。 接下来𝑛行每行一个长度为𝑚的01 字符串。第𝑖行第𝑗个字符是0 表示坐标 (𝑖, 𝑗)的格子不是障碍,否则表示是障碍。 输入保证(1,1)不是障碍且至少有一个障碍。
扫地机器人 (robot) 【输出格式】 对于每组测试数据,输出一行一个整数表示答案,答案可能很大,对 998,244,353 取模后输出。 【样例输入】 2 2 4 0111 1111 2 4 0010 1000 【样例输出】 2 5 【样例说明】 𝑛= 2, 𝑚= 4时,一共有两种合法的方案:
在第一种方案中,机器人在撞上障碍(1,3)之前,一共经过了4 个格子。在第 二种方案中,机器人在撞上障碍(2,1)之前,一共经过了1 个格子。因此第二组测 试数据的答案为1 + 4 = 5。 【数据规模】 测试数据1 (20%):𝑛≤4, 𝑚≤4。 测试数据2 (30%):𝑛≤50, 𝑚≤50,且除了(1,1)外所有格子都是障碍。 测试数据3 (50%):𝑛≤50, 𝑚≤50。 对于所有测试数据,𝑇≤10。