版权声明

本题版权归 所有。

题目来源：http://124.220.38.118:25565/contest/69d393c30dc210c7ec3aa396

注意

本题有加强版：

题目描述

给定一个 $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