你即將在一個長方形場館中舉行一場國際程式競賽,場館可容納 HW 個座位,安排成 H 個橫列和 W 個直行。橫列編號為 1 到 H,直行編號為 1 到 W。在橫列 r 和直行 c 的座位用 (r,c) 標記。你邀請了 HW 位選手,編號為 1 到 HW,你也做了一張座位圖,座位圖中每個座位恰好指定一位選手。
場館中的一組座位 S 可被稱作「長方形」,如果存在整數 r1,r2,c1,c2 滿足以下條件:
我們說一組長方形的 k 個座位 (1≤k≤HW) 是「美麗的」,如果座位指定在這組的選手編號是一組連續正整數的排列,即若我們把這 k 個座位上的選手蒐集起來丟進一個序列 B,並加以排序的話,那 B1=B2−1,B2=B3−1,…,Bi−1=Bi−1,…,B|B|−1=B|B|−1 將會成立。座位圖的「美麗程度」則是圖中可找出的美麗長方形座位組的個數。
你的目標是計算座位圖的「美麗程度」。
輸入首行兩個正整數 H,W,變數意義如題目所敘。
接下來 H 行,每行 W 個數字以單一空格隔開,代表座位圖的內容。
輸出座位圖的「美麗程度」。
範測測資一中,形成矩形的連續正整數區間分別如下: [1,1],[1,8],[1,12],[2,2],[3,3],[4,4],[5,5],[6,6],[6,7],[7,7], [8,8],[9,9],[9,10],[9,11],[9,12],[10,10],[11,11],[11,12],[12,12]
IOICamp 2020 Day4 pF