Educational-Codeforces-Round-#133C题解

Educational Codeforces Round #133 C. Robot in a Hallway

题目大意

有一个$2*m$的网格，一个机器人在$(1,1)$的位置，现在想要走遍所有的格子，且每个格子最多只能经过一次。

对于每个格子$(i,j)$存在$a_{i,j}$，表示至少经过$a_{i,j}$秒后才能进入这个格子。

每一秒内，机器人有两种动作；

• 待在当前格子不动
• 去往上下左右任意相邻的格子

求出走遍每一个格子的最小时间。

数据规模

有$t$组数据: $1\leq t \leq 10^4$

$2 \leq m \leq 2 * 10^5$

$0 \leq a_{i,j} \leq 10^9$

$\Sigma m \leq 2 * 10^5$

我的思路（错）

由题意易得有三种遍历方法

• 1. 顺时针走， 如;

  1 -> 2 -> 3 -> 4
  			   |
  8 <- 7 <- 6 <- 5

• 2. 逆时针走，如:

  1 <- 8 <- 7 <- 6
  |			   |
  2 -> 3 -> 4 -> 5

• 3. 绕着走，如:

  1	 4 -> 5	   8
  |	 |	  |    |
  2 -> 3	  6 -> 7

假设所有$a$均为零，可以得出每种方法走到每个格子对应的时间$s1_{i,j}$，$s2_{i,j}$，$s3_{i,j}$，

接着，对于每种方法，遍历每个格子，对于任意$(i,j)$，求出其中$a_{i, j} - s_{i, j}$的最大值，即等待时间的最大值，若$a_{i, j} \leq s_{i, j}$,则按0算

求出三种方法对应的最大等待时间后，则可以假设开始时等待到某一时刻后，直接畅通无阻地走完格子。所以，对于每种方法，花费的时间为$2 * n - 1 + max(s_{i, j})$

时间复杂度为$\Theta (n)$

代码链接

！！！不止三种方法！！！

可以先用第三种，再用第二或第三种。

大佬代码

Um_nik

对于每种走法，都能简化为先蛇行走，之后在某一结点按钩子形走。

所以可以得出状态转移方程。