問題一覧 > 教育的問題

No.2913 Two-Dimensional Metric Space

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 42
作問者 : 👑 p-adic / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10038 / 自分の提出
問題文最終更新日: 2024-06-15 16:26:59
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 449 (順位表) の他の問題:

Problem Statement

At the beginning of the input, $2$ positive integers $H, W$ are given.

There is a grid with $H$ rows and $W$ columns. For each positive integer $i$ not greater than $H$ and each positive integer $j$ not greater than $W$, the cell that is $i$-th from the top and $j$-th from the left is denoted by cell $(i,j)$.

You are initially at cell $(1,1)$ and want to reach cell $(H,W)$ by repeatedly moving only to a cell adjacent vertically or horizontally.

　

However, some cells have holes. You cannot move outside the cells or to a cell with a hole.

The information on whether each cell has a hole is given as $H$ strings of length $W$ consisting only of . and #. For any positive integer $i$ not greater than $H$, letting $S_i$ be the $i$-th given string, for any positive integer $j$ not greater than $W$, the $j$-th character from the left of $S_i$ being # is equivalent to cell $(i,j)$ having a hole.

　

Determine whether you can move from cell $(1,1)$ to cell $(H,W)$, and if you can, find

  • the minimum number $X$ of horizontal moves when moving from cell $(1,1)$ to cell $(H,W)$, and
  • the minimum number $Y$ of vertical moves when moving from cell $(1,1)$ to cell $(H,W)$ so that the number of horizontal moves is $X$.

Input

The input is given from standard input in $1 + H$ lines in the following format:

  • Line $1$ contains $H, W$ separated by a single space.
  • For each positive integer $i$ not greater than $H$, line $1 + i$ contains $S_i$.
$H$ $W$
$S_1$
$\vdots$
$S_H$

Constraints

The input satisfies the following constraints:

  • $H$ is an integer satisfying $2 \leq H \leq 500$.
  • $W$ is an integer satisfying $2 \leq W \leq 500$.
  • For any positive integer $i$ not greater than $H$, $S_i$ is a string of length $W$ consisting only of . and #.
  • The $1$-st character from the left of $S_1$ is ..
  • The $W$-th character from the left of $S_H$ is ..

Output

If you cannot move from cell $(1,1)$ to cell $(H,W)$, print No. 

No

If you can, print Yes on line $1$, and print $X,Y$ separated by a single space on line $2$. 

Yes
$X$ $Y$

Print a newline at the end.

Sample

Sample 1
Input
2 2
..
..
Output
Yes
1 1

Since there are no holes anywhere, you can reach $(H,W) = (2,2)$, for example, by moving so that the pair of row and column numbers changes as $(1,1) \mapsto (1,2) \mapsto (2,2)$. In this case, the number of horizontal moves and the number of vertical moves are both $1$. There is no way of moving with fewer than $1$ horizontal moves. Also, there is no way of moving with exactly $1$ horizontal move and fewer than $1$ vertical moves.

Sample 2
Input
2 2
.#
#.
Output
No

You are initially at cell $(1,1)$, and you cannot move because all the vertically or horizontally adjacent cells have holes.

Sample 3
Input
9 7
.......
.#####.
.####..
.####.#
.####..
.#...#.
.#.#.#.
.#.#.#.
...#...
Output
Yes
6 14

Note that $(X,Y) \neq (8,8)$. $6$ is smaller than $8$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。