SP16208 DCEPC11C - Challenge Accepted

Aman 和 Arpit 对编程感到厌倦了，他们觉得再没有新的挑战。即使那些对大多数人来说极其困难的问题，对他们而言也只是小菜一碟。随着 ICPC 的临近，他们的队友 Sameer 对此感到担心。为了重新激发他们的编程兴趣，Sameer 向他们发起了一个游戏挑战。 这个游戏是在一个 $N \times M$ 的网格上进行的（共有 $N$ 行 $M$ 列）。在这个网格中的一些单元格里放有硬币。可以假设所有硬币都是一样的。Sameer 还给了他们另一种硬币排列的同样大小的网格。任务很简单：通过移动硬币，将初始网格变换为最终网格。硬币移动的规则如下： 1. 每次只允许移动一枚硬币。 2. 每次硬币可以向上、下、左或右移动一格，前提是目标单元格为空。 3. 如果目标单元格已被另一枚硬币占据，当前硬币可以跳过这枚硬币，直到落在一个空单元格中。事实上，硬币可以连续跳过任意数量的硬币，直到找到一个空的位置。硬币不能跳过空单元格。无论跳过多少个硬币，此过程都只算作一次移动。 最先以最少移动次数完成挑战的人将获得 Sameer 的奖励。因此，Aman 和 Arpit 立刻开始编写代码解决这个问题。你能帮助他们预测将初始网格转换为最终网格所需的最少移动次数吗？

第一行是一个整数 $T$，表示测试用例的数量。 接下来，每个测试用例的第一行有两个整数 $N$ 和 $M$，中间用空格隔开。 随后有 $2 \times N$ 行描述每个测试用例。前 $N$ 行代表初始网格，后 $N$ 行代表最终网格。 网格中的每个字符要么是 ‘C’（表示该单元格有硬币），要么是 ‘.’（表示该单元格为空）。

对于每个测试用例，输出一个整数，表示将初始网格转换为最终网格所需的最小移动次数。如果无法完成转换，输出 `-1`。 **本翻译由 AI 自动生成**