#LQB0036. 采摘园

采摘园

题目描述:

有一个矩形的采摘园,采摘园里有N排M列果树,其中有梨树和苹果树,一天小青要去采摘园采摘果子,到了采摘园,看到提示牌写的:
1.只可以采摘苹果,梨树暂不能采摘(未成熟);
2.采摘的起点是从采摘园中指定的某一颗苹果树;
3.从起点开始可以向上、向下、向左、向右移动(只能在采摘园中移动),且只能在苹果树下移动,不能越过梨树。

编写一个程序,计算小青从起点出发最多可到达多少棵苹果下采摘(包括起点苹果树)。
例如:矩形的采摘园种有3排4列的果树,用数字“1”表示苹果树,用数字“2”表示梨树,用数字“6”表示起点(起点也是苹果树),故从起点出发最多可到达7棵苹果下采摘(包含起点苹果树)。

如图所示

输入格式

第一行输入两个正整数 N,MN,M(以空格分隔),表示采摘园的行数与列数。
接下来 NN 行,每行输入 MM 个数字(以空格分隔),每个数字为 126,分别表示苹果树、梨树与起点。

输出格式

输出一个整数,表示从起点出发最多可到达的苹果树格子数量(包含起点)。

样例输入输出

样例输入1

3 4
2 1 2 1
1 6 1 2
1 1 1 2

样例输出1

7

数据范围与测试点说明

  • 3N503\le N\le 50
  • 3M503\le M\le 50
  • 矩阵元素只可能为 126,且恰好有一个 6

时间限制与内存限制

  • 时间限制:11
  • 内存限制:10241024 KiB