問題一覧 > 通常問題

No.2708 Jewel holder

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 172
作問者 : 👑 Nafmo2Nafmo2 / テスター : dyktr_06dyktr_06 sepa38sepa38 ryota2357ryota2357
0 ProblemId : 9985 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-31 13:39:57

問題文

縦 $H$ 行 横 $W$ 列のグリッドがあります.上から $i$ 行目 左から $j$ 列目のマスを $(i,j)$ で表します.
o が書いてあるマスに到達すると宝石を1つ受け取り,x が書いてあるマスに到達すると宝石を1つ没収されます.

各 $i,j (1 \leq i \leq H, 1\leq j \leq W)$ について、マス $(i,j)$ の情報が文字 $A_{i,j}$ によって与えられます.

$A_{i,j}$ が o ならば,マス $(i,j)$ に到達した時必ず宝石を1つ受け取り,$A_{i,j}$ が x ならば,マス $(i,j)$ に到達した時必ず宝石を1つ没収されます.

マス $(1,1)$ は必ず宝石がもらえる o マスであることが保証されています.
また,マス $(1,1)$ および マス $(H,W)$ は必ず # マスでないことが保証されています.

Nafmoくんは宝石を $0$ 個持っている状態で,マス $(1,1)$ に到達し宝石を$1$つ受け取りました.
Nafmoくんは右と下の移動を繰り返すことで,マス $(1,1)$ から マス $(H,W)$ まで最短で到達したいです.ただし,Nafmoくんが宝石を没収されるときに,$1$ つも宝石を持っていない状況が生まれる経路は無効とします.
以上の条件を満たす経路の選び方は何通りあるかを求めてください.

13:39追記:# は通ることができません.

入力

$H \ W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$\ \vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

  • $2 \leq H,W \leq 10$
  • $H,W$ は整数
  • $A_{i,j}$ は ox# のいずれか
  • $A_{1,1} = $ o
  • $A_{H,W} \neq $ #

出力

条件を満たす経路の選び方を求めて出力してください.

サンプル

サンプル1
入力
3 3
ooo
o#o
ooo
出力
2

以下の2通りとなります.

サンプル2
入力
3 3
oox
xxx
xoo
出力
3

以下の $3$ 通りで全てです.

サンプル3
入力
3 3
oxx
xxx
xxx
出力
0

どのような経路を選択しても,ゴールまでの間に宝石を支払うことができなくなってしまうため,条件を満たす経路は存在しません.

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