TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3343
  • 题目
  • P3343【THOI2012】水位
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    有一个正方形的地区,该地区特点鲜明:如果把它等分为N×N个小正方形格子的话,在每个格子内的任意地点的地表高度是相同的,并且是一个0到M之间的整数。正方形地区的外部被无限高的边界包围。
    该地区可能会有积水。经过多年的观察,人们发现了几个关于积水的重要规律:
    1. 每个格子要么完全没有积水,要么它内部的任意地点的水面高度都是相同的。并且水面高度一定大于地表高度。
    2. 每个格子的水面高度在0~M之间,并且一定是整数。
    3. 对于相邻(必须为边相邻)的两个格子,一定不会出现水自动从一个格子流向另一个格子的情况。也就是说,一定不能出现这两个格子都有水且水面高度不同,或者有水格子的水面比无水格子的地表要高的情况。
    例如,下面图中每个格子里有两个数a/b,说明该格子的地表高度是a,水面高度是b(均为海拔高度),而没有水的格子中b以“−”表示。则左边的情况是符合规律的,而右边的情况并不符合以上规律,因为水可以由2/4的格子流向3/−的格子。



    该地区水文站的工作人员小A想知道,该地区中有多少种不同的水位情况符合规律。你能回答他的这个问题吗?

    输入格式

    输入文件的第一行包含两个正整数N和M。
    随后的N行,每行包含N个非负整数。其中第i+1行的第j个数表示该地区第i行第j列格子的地表高度。

    输出格式

    输出文件只包含一个整数,即该地区符合规律的水位情况种数。

    样例输入

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

    样例输出

    6

    提示

    【样例解释】:

    【数据范围】: