注记:
本题存在赛时原版和赛后加强版两个版本,此处为赛后加强版。
测试点 1 - 2 为样例,测试点 3 - 16 满足 和 的限制,测试点 17 - 30 不满足这一限制。
由于评测机性能差异,本题的时间限制由 1 秒改为 3 秒。
在你输出一行后,请使用 fflush(stdout); / cout.flush(); / cout << endl; 清空缓冲区。
你可以尝试使用 unsigned short 存储海拔信息以优化空间常数。
Sleeping Bear 是一只十分可爱的小熊,它越吃蜂蜜就越可爱,可是它每次去摘蜂蜜都会被蜜蜂蛰一头包。今天它又要吃蜂蜜了,但是它不想又被蜜蜂蛰一头包,所以它想请你帮助它设计一条逃生路线以躲避蜜蜂的围追堵截。
给定一个正整数 ,表示有一个 的地图,其中每一格都有自己的海拔。海拔是一个 范围内的正整数。保证海拔为 的格子各有一个。
已知 Sleeping Bear 所在的位置(默认蜜蜂就在它身后),不能走的路,可以走的路以及湖的位置(只有 Sleeping Bear 跳入湖中才能不被蜜蜂蛰):
- Sleeping Bear 可能在任何一个海拔大于 而小于 的位置;
- 所有海拔不大于 的位置都被水淹没,形成了湖;
- 所有海拔不小于 的位置都被雪覆盖,形成了雪山,不能走;
- 所有海拔大于 而小于 的位置都是可以走的路;
- 保证 。
在接下来的 天里,Sleeping Bear 每天都要去吃蜂蜜,而每天的天气都不同(这导致每天的 都不同)。请你帮助 Sleeping Bear 数一数,有多少个海拔大于 而小于 的位置不存在通往湖边的路(他每次可以向上、下、左、右移动一格)。