小红走矩阵
题号:NC269999
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红来到了一个n*m的矩阵,她初始站在左上角,每次行走可以按“上下左右”中的一个方向走一步,但必须走到和当前格子不同的字符,也不能走到矩阵外。

小红想知道,从左上角走到右下角最少需要走多少步?

输入描述:

第一行输入两个正整数n,m,用空格隔开。代表矩阵的行数和列数。
接下来的n行,每行输入一个长度为m的、仅由小写字母组成的字符串,用来表示矩阵。
1\leq n,m \leq1000

输出描述:

如果无法到达右下角,则输出-1。
否则输出一个整数,代表行走的最小步数。
示例1

输入

复制
3 4
abbc
accd
bcee

输出

复制
9

说明