UOJ Logo

NOI.AC

1S 512MB

#1660. Gakkipan的迷宫

Statistics

题目描述

Gakkipan在玩一个电子游戏,他操控的人物带伤进入了一个满是陷阱的迷宫,迷宫中是一个大小为n*n的平面网格区域,入口在左上角,出口在右下角,迷宫中每个格子都可能存在着一个陷阱,每个陷阱有一个威力值a,如果踏过存在该陷阱的格子后,Gakkipan人物的伤势变为之前的a倍,若没有陷阱的格子该值表示为1,一开始Gakkipan的伤势值为1,Gakkipan的人物只能朝右或者朝下走,在到达出口后,Gakkipan有一门独门心法,可以且必须把伤势的值转化为最终伤势末尾后缀0的个数,求走出迷宫的最小伤势。

文件输入

输入第一行两个正整数n,表示迷宫的大小
接下来n行,每行n个正整数,表示迷宫中每个格子的陷阱威力值

文件输出

输出最终转化后的伤势值

输入样例

3
1 2 3
4 5 6
7 8 9

输出样例

0

数据规模

对于前30%的数据,n<=10
对于100%的数据,n<=1000,所有陷阱的威力值a<=10^9