问题 D: [小学省赛05]走迷宫

问题 D: [小学省赛05]走迷宫

时间限制: 1 Sec  内存限制: 128 MB
提交: 39  解决: 18
[提交] [状态] [讨论版] [命题人:]

题目描述

小明与许多同学一起参加者了今年的“信息与未来”小学生夏令营活动。夏令营的组织者设计了许多有趣的活动,走迷宫就是其中的一项。
迷宫由N*N个方格组成,每个方格均被组织者事先标上了“0”或“1”(左上角第一个方格和右下角最后一个方格一定是“0”)。当你进入左上角的第一方格中时,看到相邻的方格是“0”时则可以进客店,而如果是“1”则表示此路不通。
小明被告之:从迷宫的左上角第一个方格的入口处准备进入时,你可得到一个记有N*N分值的记分表,每经过一个标有“0”的记分表将自动扣去1分,当走到右下角最后一个方格的出口处时,将显示你手中的记分表剩余的分值。
夏令营的组织者将只奖励所有参加此项活动中,记分表剩余的分值最多的营员。

输入

第一行是一个整数N(3<=n<=40),接下来有N行,每行均有N个由0和1组成的数据。

输出

一个整数(记分表剩的分值)

样例输入

4
0011
1000
0001
1000

样例输出

9

[提交][状态]