問題一覧 > 通常問題

No.1323 うしらずSwap

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : ei1333333ei1333333 / テスター : LuzhiledLuzhiled
2 ProblemId : 4176 / 出題時の順位表
問題文最終更新日: 2020-12-20 01:08:02

問題文

$H$ 行 $W$ 列のマス目があります。上から $r \ (1 \leq r \leq H)$ 行目、左から $c\ (1 \leq c \leq W)$ 列目にあるマスを $(r, c)$ で表します。

マス目の状態は二次元配列 $S$ で表されます。$S_{r,c}$ が # のときマス $(r, c)$ には障害物があり、. のとき障害物はありません。 マス目の外周は障害物 # で囲まれていることが保証されます。

マス上のうしさんとひかりちゃんはお互いのいる場所の交換をしようとしています。

最初、うしさんはマス $(r_a, c_a)$、ひかりちゃんはマス $(r_b, c_b)$ にいます。$2$ 人は、自分が現在いるマスに辺で隣接している $4$ マスのうち、障害物がなく誰もいないマスにのみ移動できます。 $2$ 人は好きな順番で移動することができますが、$2$ 人が同時に別のマスに移動することはできません。最終的に、うしさんはマス $(r_b, c_b)$、ひかりちゃんはマス $(r_a, c_a)$ にいるようにしたいです。

場所の交換ができるか判定し、できる場合は場所の交換にかかる $2$ 人の移動回数の和の最小値を求めてください。

入力

$H$ $W$ $r_a$ $c_a$ $r_b$ $c_b$
$S_{1,1} S_{1,2} \cdots S_{1,W}$
$S_{2,1} S_{2,2} \cdots S_{2,W}$
$:$
$S_{H,1} S_{H,2} \cdots S_{H,W}$
  • $4 \leq H, W \leq 1333$
  • $1 \lt r_a, r_b \lt H$
  • $1 \lt c_a, c_b \lt W$
  • $(r_a, c_a) \neq (r_b, c_b)$
  • $S_{r,c}$ $(1 \leq r \leq H, 1 \leq c \leq W)$ は # または .
  • $S_{r_a, c_a}, S_{r_b, c_b}$ は .
  • マス目の外周 ($1$ 行目, $H$ 行目, $1$ 列目, $W$ 列目) は #
  • $H, W, r_a, c_a, r_b, c_b$ は整数

出力

$1$ 行に、場所の交換にかかる $2$ 人の移動回数の和の最小値を出力してください。 ただし、場所の交換ができない場合は $-1$ を出力してください。

サンプル

サンプル1
入力
4 5 2 2 3 4
#####
#...#
##..#
#####
出力
6

例えば、次のような移動をします。

  1. うしさんの移動: $(2, 2) \Rightarrow (2, 3)$
  2. うしさんの移動: $(2, 3) \Rightarrow (2, 4)$
  3. ひかりちゃんの移動: $(3, 4) \Rightarrow (3, 3)$
  4. うしさんの移動: $(2, 4) \Rightarrow (3, 4)$
  5. ひかりちゃんの移動: $(3, 3) \Rightarrow (2, 3)$
  6. ひかりちゃんの移動: $(2, 3) \Rightarrow (2, 2)$
サンプル2
入力
4 5 2 2 2 4
#####
#.#.#
#...#
#####
出力
-1

両者が同時に同じマスに留まることはできません。

サンプル3
入力
5 4 4 3 2 3
####
#..#
#..#
#..#
####
出力
6

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