分类: 题解

68 篇文章

CodeForces – 1623D – Robot Cleaner Revisit
地板有 $n$ 行 $m$ 列,一个机器人被安置在坐标 $(r_b, c_b)$,还有一个障碍位于 $(r_d, c_d)$。
每过一秒,机器人的坐标会 $(r, c)\rightarrow (r+d_r, c+d_c)$。
初始时 $d_r=d_c=1$,当机器人到达边界后,$d_r,d_c$ 会变化:
  • 若机器人碰到上/下边界($r=1$ 或 $r=n$),下一秒 $d_r\leftarrow -d_r$,
  • 若机器人到达左/右边界($c=1$ 或 $c=m$),下一秒 $d_c\leftarrow -d_c$.
每一秒内,位于 $(r,c)$ 的机器人有 $\frac{p}{100}$ 的概率,成功清理掉位于第 $r$ 行和第 $c$ 列的障碍,之后,它将按照上面的规则进行移动。
若每次清理的结果相互独立,求清理掉障碍物 $(r_d, c_d)$ 所需的期望时间。