1395: 拯救大熊猫

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

    保护区里生活着很多珍稀保护动物,乌拉尔巡山时发现大熊猫佳佳被偷猎者捕走了,在寻找过程中,乌拉尔拣到偷猎者遗失的一张手绘地图,地图由 n 行 m 列个格子构成,经过研究发现图上画的是一个迷宫,迷宫的入口在第 x 行,第 y 列,地图上每一个格子有一个字符,代表的意思如下:
    #:表示不可通行;
    数字:表示此处藏有其它珍稀保护动物的数目,可以通行;
    @:表示大熊猫佳佳的位置。
    在迷宫里每走一个格子要花 1 个单位的时间,上级要求乌拉尔在最短时间内将佳佳带回来,同时将路上遇到的所有其它珍稀保护动物一并带回, 但不能故意绕路耽误时间,由于大熊猫佳佳身上有偷猎者安装的报警装置,所以找到大熊猫佳佳的同时必须立即启动传送门将所有动物送回到保护区总部。
    请你编写代码,帮乌拉尔计算出在不违抗上级指令的条件下,最多能带回其它珍稀保护动物的数目,假设一定存在一条从入口到佳佳位置的路径。

输入格式

    第一行,4 个整数 n、m、x、y 由一个空格分隔,n 代表迷宫的行数,m 代表迷宫的列数,x 和 y 代表迷宫入口的行坐标和列坐标,迷宫的行号和列号从 1 开始编号。
    接下来 n 行,每行 m 个字符,用一个空格分隔的。其中字符#表示不可通行,数字表示此处藏有珍稀保护动物的数目(0 表示无动物可以通行),@表示佳佳的位置。

输出格式

    一个整数,代表乌拉尔能带回珍稀保护动物的数目(不含大熊猫佳佳)。

输入样例 复制

3 3 1 1
0 2 #
1 2 #
# @ 1

输出样例 复制

4

数据范围与提示

    样例解释:
        从入口(1,1)到@处乌拉尔能带回 4 只其它保护动物,路线为(1,1)→(1,2)→(2,2)→(3,2)。
    数据规模:
        对于 30%的数据,1 ≤ n,m,x,y ≤ 10,0 ≤ 地图中的数字 ≤ 9。
        对于 50%的数据,1 ≤ n,m,x,y ≤ 15,0 ≤ 地图中的数字 ≤ 9。
        对于 100%的数据,1 ≤ n,m,x,y ≤ 100,0 ≤地图中的数字 ≤ 9。

分类标签