AT_mujin_pc_2018_c.右折

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

有一个 $N$ 行 $M$ 列的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作 $(i, j)$ 。特别地，左上角的格子是 $(1, 1)$ ，右下角的格子是 $(N, M)$ 。网格的状态由一个二维数组 $s$ 表示，当 $s_{ij}$ 为 # 时，表示格子 $(i, j)$ 上有障碍物；为 . 时，表示没有障碍物。

高桥君在这个网格的某个格子上放置了一个机器人，并让机器人朝上下左右任意一个方向。机器人会沿着它面朝的方向直走至少 $1$ 格，然后向右转 $90$ 度，再沿新方向直走至少 $1$ 格后停下。在这个过程中，机器人经过的所有格子（包括起始格和停止格）都没有障碍物，且机器人不会走出网格。

请你计算，机器人可能的起始格和停止格的有序对的数量。

输入格式

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

$N$ $M$
$s_{11}\ldots s_{1M}$
$s_{21}\ldots s_{2M}$
$\vdots$
$s_{N1}\ldots s_{NM}$

输出格式

输出机器人可能的起始格和停止格的有序对的数量。

输入输出样例

输入#1
```
3 3
..#
...
#.#
```
输出#1
```
9
```
输入#2
```
2 5
.#.#.
..#..
```
输出#2
```
2
```

输入#3

6 8
#......#
##....##
#.#..#.#
#..##..#
#......#
#......#

输出#3

说明/提示

限制条件

$2 \leq N, M \leq 2 \times 10^3$
$s_{ij}$ 只会是 # 或 .

样例解释 1

$((1,1),(2,2)),((1,1),(3,2)),((1,2),(2,1)),((2,1),(1,2)),((2,1),(3,2)),((2,2),(1,1)),((2,3),(1,2)),((2,3),(1,1)),((3,2),(2,3))$ 共 $9$ 个满足条件的有序对。

由 ChatGPT 4.1 翻译

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

首页