Robot in a Hallway

题意翻译

# Robot in a Hallway ## 题目描述 有一$ 2 $行$m$列的网格，从上到下编号为$1$至$2$，从左往右编号为$1$至$m$。 机器人开始时在网格$(1,1)$内。一秒内，它可以进行如下任意一个动作： - 走到上、下、左、右任意相邻的网格 - 待在网格内不动 开始时，除了网格$(1,1)$其他格子都是锁着的。每个网格$(i,j)$有一个值$a{i,j}$，表示该网格解锁的时间。只有经过至少$a_{i,j}$秒后，机器人才可以进入网格$(i,j)$。 机器人要走遍所有网格，且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。 实现如上操作的最快时间是什么？ ## 输入格式 第一行是一个整数$ t $ ( $ 1 \le t \le 10^4 $ )，表示测试样例的个数。 每个样例的第一行是一个整数$ m $ ( $ 2 \le m \le 2 \cdot 10^5 $ )，表示网格的列数。 下面两行中的第$i$行有$m$个整数$ a_{i,1}, a_{i,2}, \dots, a_{i,m} $( $ 0 \le a_{i,j} \le 10^9 $ )，表示每个格子解锁的时间。$a_{i,1}=0$。如果$a_{i,j}=0$，表示网格$(i,j)$一开始就是解锁的。 所有测试样例中$m$的和不超过$2 \cdot 10^5$ ## 输出格式 对于每个测试样例，输出一个整数：机器人走遍每一个网格且每个网格只被访问一次的最小时间。

题目描述

There is a grid, consisting of $ 2 $ rows and $ m $ columns. The rows are numbered from $ 1 $ to $ 2 $ from top to bottom. The columns are numbered from $ 1 $ to $ m $ from left to right. The robot starts in a cell $ (1, 1) $ . In one second, it can perform either of two actions: - move into a cell adjacent by a side: up, right, down or left; - remain in the same cell. The robot is not allowed to move outside the grid. Initially, all cells, except for the cell $ (1, 1) $ , are locked. Each cell $ (i, j) $ contains a value $ a_{i,j} $ — the moment that this cell gets unlocked. The robot can only move into a cell $ (i, j) $ if at least $ a_{i,j} $ seconds have passed before the move. The robot should visit all cells without entering any cell twice or more (cell $ (1, 1) $ is considered entered at the start). It can finish in any cell. What is the fastest the robot can achieve that?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ m $ ( $ 2 \le m \le 2 \cdot 10^5 $ ) — the number of columns of the grid. The $ i $ -th of the next $ 2 $ lines contains $ m $ integers $ a_{i,1}, a_{i,2}, \dots, a_{i,m} $ ( $ 0 \le a_{i,j} \le 10^9 $ ) — the moment of time each cell gets unlocked. $ a_{1,1} = 0 $ . If $ a_{i,j} = 0 $ , then cell $ (i, j) $ is unlocked from the start. The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

输入输出样例

输入样例 #1

4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0

输出样例 #1

5
19
17
3