A6445 | 「CodePlus 2017 12 月赛」白金元首与独舞
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
> 到河北省 见斯大林 / 在月光下 你的背影 / 让我们一起跳舞吧
うそだよ\~ 河北省怎么可能有 Stalin。
可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢？
怀揣着这份小小的希望，元首 Adolf 独自走进了花园。终有一天会重逢的吧，Stalin。或许是在此处，或许是在遥远的彼方。
无论如何，在此之前，好好装点一番花园，编排一段优美的舞步吧！
<hr style='color: #ddd; margin-bottom: 1em'>
元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识，指向上、下、左、右四个方向中的任意一个。元首位于一个格子时，会按照其中标识所指的方向进入周围的格子，或者走出花园（即目的格子不在网格之内）。举个例子 —— 对于下面的放置方式，元首从第 $3$ 行第 $2$ 列的格子开始，会沿着以红色标出的路径走出花园；从第 $2$ 行第 $2$ 列的格子开始，则会在以蓝色标出的环路内不断地行走。
<div style='text-align: center; font-size: 1.6em'>← <span style='color: blue'>→</span> <span style='color: blue'>↓</span><br><br>← <span style='color: blue'><strong>↑</strong></span> <span style='color: blue'>←</span><br><br><span style='color: red'>↓</span> <span style='color: red'><strong>←</strong></span> ↑<br><br><span style='color: red'>→</span> <span style='color: red'>↓</span> ←<br><br></div>
元首已经设计好了大部分格子的标识。元首用字符
你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子，使得两个方案中该格子内的标识不同。当然，由于答案可能很大，只需给出方案数除以 $10^9 + 7$ 所得的余数即可。
うそだよ\~ 河北省怎么可能有 Stalin。
可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢？
怀揣着这份小小的希望，元首 Adolf 独自走进了花园。终有一天会重逢的吧，Stalin。或许是在此处，或许是在遥远的彼方。
无论如何，在此之前，好好装点一番花园，编排一段优美的舞步吧！
<hr style='color: #ddd; margin-bottom: 1em'>
元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识，指向上、下、左、右四个方向中的任意一个。元首位于一个格子时，会按照其中标识所指的方向进入周围的格子，或者走出花园（即目的格子不在网格之内）。举个例子 —— 对于下面的放置方式，元首从第 $3$ 行第 $2$ 列的格子开始，会沿着以红色标出的路径走出花园；从第 $2$ 行第 $2$ 列的格子开始，则会在以蓝色标出的环路内不断地行走。
<div style='text-align: center; font-size: 1.6em'>← <span style='color: blue'>→</span> <span style='color: blue'>↓</span><br><br>← <span style='color: blue'><strong>↑</strong></span> <span style='color: blue'>←</span><br><br><span style='color: red'>↓</span> <span style='color: red'><strong>←</strong></span> ↑<br><br><span style='color: red'>→</span> <span style='color: red'>↓</span> ←<br><br></div>
元首已经设计好了大部分格子的标识。元首用字符
L、R、U、D 分别表示指向左、右、上、下四个方向的标识，用字符 . 表示未决定的格子。现在，元首希望将每个 . 替换为 L、R、U、D 中任意一种，使得从花园中的任意一个格子出发，按照上述规则行走，都可以最终走出花园。你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子，使得两个方案中该格子内的标识不同。当然，由于答案可能很大，只需给出方案数除以 $10^9 + 7$ 所得的余数即可。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 $T$ —— 测试数据的组数。接下来包含 $T$ 组测试数据，格式如下，测试数据间没有空行。
* 第 $1$ 行：两个空格分隔的正整数 $n$、$m$ —— 依次表示花园被分成的行数和列数。
* 接下来 $n$ 行：每行一个长度为 $m$ 的由字符
输入的第一行包含一个正整数 $T$ —— 测试数据的组数。接下来包含 $T$ 组测试数据，格式如下，测试数据间没有空行。
* 第 $1$ 行：两个空格分隔的正整数 $n$、$m$ —— 依次表示花园被分成的行数和列数。
* 接下来 $n$ 行：每行一个长度为 $m$ 的由字符
L、R、U、D 和 . 组成的字符串 —— 表示花园内已经确定的格子状态。输出格式
输出到标准输出。
对于每组测试数据输出一行 —— 满足条件的方案数除以 $10^9 + 7$ 所得的余数。
对于每组测试数据输出一行 —— 满足条件的方案数除以 $10^9 + 7$ 所得的余数。
输入输出样例
输入 #1
5 3 9 LLRRUDUUU LLR.UDUUU LLRRUDUUU 4 4 LLRR L.LL RR.R LLRR 4 3 LRD LUL DLU RDL 1 2 LR 2 2 .. ..
输出 #1
3 8 0 1 192
令 $k$ 表示标记未确定（即包含 “
对于所有数据，有 $1 \leq T \leq 10$，$1 \leq n, m \leq 200$，$0 \leq k \leq \min(nm, 300)$。
<!-- BEGIN: Migrated markdown table -->
| 测试点编号 | $n$, $m$ | $k$ | 特殊约定 |
|-|-|-|-|
| 1 | $\leq 50$ | $= 0$ | 无 |
| 2 | $\leq 200$ | $= 0$ | 无 |
| 3 | $\leq 2$ | $\leq 4$ | 无 |
| 4 | $\leq 4$ | $\leq 7$ | 无 |
| 5 | $\leq 10$ | $\leq 7$ | 无 |
| 6 | $\leq 10$ | $\leq 7$ | 无 |
| 7 | $\leq 10$ | $\leq 100$ | 无 |
| 8 | $\leq 10$ | $\leq 100$ | 无 |
| 9 | $\leq 10$ | $\leq 100$ | 无 |
| 10 | $\leq 10$ | $\leq 100$ | 无 |
| 11 | $\leq 200$ | $\leq 200$ | $n = 1$ |
| 12 | $\leq 200$ | $\leq 200$ | $n = 1$ |
| 13 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 14 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 15 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 16 | $\leq 200$ | $\leq 300$ | 无 |
| 17 | $\leq 200$ | $\leq 300$ | 无 |
| 18 | $\leq 200$ | $\leq 300$ | 无 |
| 19 | $\leq 200$ | $\leq 300$ | 无 |
| 20 | $\leq 200$ | $\leq 300$ | 无 |
<!-- Migrated from original HTML table:
<table class="ui celled center aligned table"><thead><tr><th rowspan="1">测试点编号</th><th rowspan="1">$n$, $m$ </th><th rowspan="1">$k$ </th><th rowspan="1">特殊约定</th></tr></thead><tbody><tr><td rowspan="1">1</td><td rowspan="1">$\leq 50$ </td><td rowspan="2">$= 0$ </td><td rowspan="10">无</td></tr><tr><td rowspan="1">2</td><td rowspan="1">$\leq 200$ </td></tr><tr><td rowspan="1">3</td><td rowspan="1">$\leq 2$ </td><td rowspan="1">$\leq 4$ </td></tr><tr><td rowspan="1">4</td><td rowspan="1">$\leq 4$ </td><td rowspan="3">$\leq 7$ </td></tr><tr><td rowspan="1">5</td><td rowspan="6">$\leq 10$ </td></tr><tr><td rowspan="1">6</td></tr><tr><td rowspan="1">7</td><td rowspan="4">$\leq 100$ </td></tr><tr><td rowspan="1">8</td></tr><tr><td rowspan="1">9</td></tr><tr><td rowspan="1">10</td></tr><tr><td rowspan="1">11</td><td rowspan="10">$\leq 200$ </td><td rowspan="5">$\leq 200$ </td><td rowspan="2">$n = 1$ </td></tr><tr><td rowspan="1">12</td></tr><tr><td rowspan="1">13</td><td rowspan="3">有且仅有第 $1$ 行的所有格子中标记未确定</td></tr><tr><td rowspan="1">14</td></tr><tr><td rowspan="1">15</td></tr><tr><td rowspan="1">16</td><td rowspan="5">$\leq 300$ </td><td rowspan="5">无</td></tr><tr><td rowspan="1">17</td></tr><tr><td rowspan="1">18</td></tr><tr><td rowspan="1">19</td></tr><tr><td rowspan="1">20</td></tr></tbody></table>
-->
<!-- END: Migrated markdown table -->
“_... wie Stalin!_”
题面与史实无关。
<hr style='color: #ddd; margin-bottom: 1em'>
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/吕时清 命题/吕时清 验题/王聿中，杨景钦
Git Repo：https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。
.”）的格子总数。对于所有数据，有 $1 \leq T \leq 10$，$1 \leq n, m \leq 200$，$0 \leq k \leq \min(nm, 300)$。
<!-- BEGIN: Migrated markdown table -->
| 测试点编号 | $n$, $m$ | $k$ | 特殊约定 |
|-|-|-|-|
| 1 | $\leq 50$ | $= 0$ | 无 |
| 2 | $\leq 200$ | $= 0$ | 无 |
| 3 | $\leq 2$ | $\leq 4$ | 无 |
| 4 | $\leq 4$ | $\leq 7$ | 无 |
| 5 | $\leq 10$ | $\leq 7$ | 无 |
| 6 | $\leq 10$ | $\leq 7$ | 无 |
| 7 | $\leq 10$ | $\leq 100$ | 无 |
| 8 | $\leq 10$ | $\leq 100$ | 无 |
| 9 | $\leq 10$ | $\leq 100$ | 无 |
| 10 | $\leq 10$ | $\leq 100$ | 无 |
| 11 | $\leq 200$ | $\leq 200$ | $n = 1$ |
| 12 | $\leq 200$ | $\leq 200$ | $n = 1$ |
| 13 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 14 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 15 | $\leq 200$ | $\leq 200$ | 有且仅有第 $1$ 行的所有格子中标记未确定 |
| 16 | $\leq 200$ | $\leq 300$ | 无 |
| 17 | $\leq 200$ | $\leq 300$ | 无 |
| 18 | $\leq 200$ | $\leq 300$ | 无 |
| 19 | $\leq 200$ | $\leq 300$ | 无 |
| 20 | $\leq 200$ | $\leq 300$ | 无 |
<!-- Migrated from original HTML table:
<table class="ui celled center aligned table"><thead><tr><th rowspan="1">测试点编号</th><th rowspan="1">$n$, $m$ </th><th rowspan="1">$k$ </th><th rowspan="1">特殊约定</th></tr></thead><tbody><tr><td rowspan="1">1</td><td rowspan="1">$\leq 50$ </td><td rowspan="2">$= 0$ </td><td rowspan="10">无</td></tr><tr><td rowspan="1">2</td><td rowspan="1">$\leq 200$ </td></tr><tr><td rowspan="1">3</td><td rowspan="1">$\leq 2$ </td><td rowspan="1">$\leq 4$ </td></tr><tr><td rowspan="1">4</td><td rowspan="1">$\leq 4$ </td><td rowspan="3">$\leq 7$ </td></tr><tr><td rowspan="1">5</td><td rowspan="6">$\leq 10$ </td></tr><tr><td rowspan="1">6</td></tr><tr><td rowspan="1">7</td><td rowspan="4">$\leq 100$ </td></tr><tr><td rowspan="1">8</td></tr><tr><td rowspan="1">9</td></tr><tr><td rowspan="1">10</td></tr><tr><td rowspan="1">11</td><td rowspan="10">$\leq 200$ </td><td rowspan="5">$\leq 200$ </td><td rowspan="2">$n = 1$ </td></tr><tr><td rowspan="1">12</td></tr><tr><td rowspan="1">13</td><td rowspan="3">有且仅有第 $1$ 行的所有格子中标记未确定</td></tr><tr><td rowspan="1">14</td></tr><tr><td rowspan="1">15</td></tr><tr><td rowspan="1">16</td><td rowspan="5">$\leq 300$ </td><td rowspan="5">无</td></tr><tr><td rowspan="1">17</td></tr><tr><td rowspan="1">18</td></tr><tr><td rowspan="1">19</td></tr><tr><td rowspan="1">20</td></tr></tbody></table>
-->
<!-- END: Migrated markdown table -->
“_... wie Stalin!_”
题面与史实无关。
<hr style='color: #ddd; margin-bottom: 1em'>
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/吕时清 命题/吕时清 验题/王聿中，杨景钦
Git Repo：https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？