201007 - 猫和老鼠

设’C’为猫,’M’为老鼠,’*’为障碍,’. ’为空地,猫和老鼠在10×10的矩阵中,例如:

  *...*.....
  ......*...
  ...*...*..
  ..........
  ...*.C....
  *.....*...
  ...*......
  ..M......*
  ...*.*....
  .*.*......

初始时猫和老鼠都面向北方(矩阵为上北下南,左西右东),它们每秒钟各走一格,如果在某一秒末它们在同一格中,那么猫就抓住老鼠了(“对穿”是不算的)。猫和老鼠的移动方式相同:平时沿直线走,下一步如果会碰到障碍物或者出界, 就用1秒的时间做一个右转90度。

试计算猫抓住老鼠需要多少秒。

输入

第一行为一整数N(N≤10),表示有N组测试数据。   每组测试数据为10行,格式如题目描述。

输出

如果100步内无解,输出-1,否则输出猫抓住老鼠的时间。

样例

输入

1
  *...*.....
  ......*...
  ...*...*..
  ..........
  ...*.C....
  *.....*...
  ...*......
  ..M......*
  ...*.*....
  .*.*......

输出

49
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题