题目详情题解（0）讨论（0）提交记录（0）

AT_abc429_f.[ABC429F] Shortest Path Query

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个包含三行 NN 列的网格。我们用从上到下的第 ii 行、从左到右的第 jj 列的单元格记作 (i,j)(i,j)。若 Si,jS_{i,j} 为 #，则 (i,j)(i,j) 是墙格，否则为 . 时，(i,j)(i,j) 是空格且可通过。

现在有 QQ 个查询，请按顺序依次处理。

每个查询给出整数 rr 和 cc，你需要将 (r,c)(r,c) 这一格的状态反转。如果该格原本是墙格，请改为空格，原本是空格则改为墙格。然后，输出以下问题的答案：

设你从 (1,1)(1,1) 出发，每次只能走到相邻的上、下、左、右的空格，能否到达 (3,N)(3,N)？如果能到达，请输出最少需要多少步。

输入格式

输入从标准输入读入，格式如下：

NN
S1,1S1,2…S1,NS_{1,1}S_{1,2}\ldots S_{1,N}
S2,1S2,2…S2,NS_{2,1}S_{2,2}\ldots S_{2,N}
S3,1S3,2…S3,NS_{3,1}S_{3,2}\ldots S_{3,N}
QQ
query1\text{query}_1
query2\text{query}_2
⋮\vdots
queryQ\text{query}_Q

每个查询的格式为：

r cr\ c

输出格式

请输出 QQ 行。

对于第 ii 次查询（1≤i≤Q1\le i\le Q），若此时 (1,1)(1,1) 无法到达 (3,N)(3,N)，请输出 -1，否则输出最少所需的步数。

输入输出样例

  • 输入#1

    5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

    输出#1

    6
10
-1

  • 输入#2

    7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

    输出#2

    10
8
10
12
-1
12

说明/提示

样例解释 1

第一次查询，将 (1,2)(1,2) 的状态反转。此时网格变为：

.....
.#.#.
...#.

此时，可以依次经过 (1,1)(1,1)、(1,2)(1,2)、(1,3)(1,3)、(1,4)(1,4)、(1,5)(1,5)、(2,5)(2,5)、(3,5)(3,5)，共需 6 步到达 (3,5)(3,5)。

第二次查询，再次将 (1,2)(1,2) 状态反转。此时网格变为：

.#...
.#.#.
...#.

此时，可以依次经过 (1,1)(1,1)、(2,1)(2,1)、(3,1)(3,1)、(3,2)(3,2)、(3,3)(3,3)、(2,3)(2,3)、(1,3)(1,3)、(1,4)(1,4)、(1,5)(1,5)、(2,5)(2,5)、(3,5)(3,5)，共需 10 步到达 (3,5)(3,5)。

第三次查询，将 (2,3)(2,3) 状态反转。此时网格变为：

.#...
.###.
...#.

此时，无论如何移动，都无法从 (1,1)(1,1) 到达 (3,5)(3,5)。

数据范围

  • 2≤N≤2×1052\le N\le 2\times 10^5
  • Si,jS_{i,j} 只可能是 # 或 .。
  • S1,1=S3,N=.S_{1,1}=S_{3,N}=.
  • 1≤Q≤2×1051\le Q\le 2\times 10^5
  • 1≤r≤31\le r\le 3
  • 1≤c≤N1\le c\le N
  • (r,c)≠(1,1), (3,N)(r,c)\neq (1,1),\ (3,N)
  • N,Q,r,cN, Q, r, c 均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页