版权声明

本题版权归 所有。

题目来源：https://oj.piaoztsdy.cn/contest/6a37fc5e728ed74d093a2b25

注意

本题有弱化版：

题目描述

给定一个 $n \times m$ 的网格，求四连通走法下从左下角（第 $n$ 行第 $1$ 列）只经过 + 或 ! 走到右上角（第 $1$ 行第 $m$ 列）需要经过的最少格子数。

特别地，当经过 ! 格子时，下一个经过的格子将被认为没有经过，但是：

• 这个格子不能是 -。
• 如果这个格子是右上角，则认为本次没有走到右上角。
• 即使这个格子是 !，也不再触发该格子的效果。

输入格式

第一行两个正整数 $n, m\ (1 \le n, m \le 1000)$。

下面一个 $n \times m$ 的字符矩阵，保证只含字符 +、-、!。

输出格式

一行一个整数表示答案。

特别地，如果无法从左下角只经过 + 或 ! 走到右上角，或者左下角是 -，或者右上角是 -，输出 $\bm{-1}$。

样例

1 1
+

1

1 1
-

-1

3 3
+++
+-+
+++

5

4 6
+++--+
+-++-+
+-++-+
+--+++

15

4 6
+-+-+-
-+-+-+
+-+-+-
-+-+-+

-1

4 6
+++-++
+-+++-
+-+--+
+--++-

11

1 1
!

1

1 10
!!!!!!!!!!

-1

1 5
!-!-!

-1

1 5
!!-!!

-1

4 6
+!!++!
++++++
++!!!+
!+++++

6

4 6
+++-++
!-+-!+
+-+-!+
!-++++

12