24093번 - 横断幕 (Banner) 다국어

문제

20XX 年,ついに IOI が JOI 国で開催されることになった.JOI 国ではこれを祝い,街中に歓迎の横断幕 (banner) をかけることにした.JOI 国では,図のように,東西方向に走る H 本の道路と,南北方向に走る W 本の道路が碁盤目状に通っている.東西方向に走る道路と南北方向に走る道路が交わるところを交差点 と呼ぶ.北から a 番目,西から b 番目の交差点を (a, b) で表す.

各交差点にはそれぞれ柱が 1 本ずつ立っている.JOI 国には国を象徴する色が黒色・灰色・白色の 3 色あ り,各柱はこの 3 色のうちのどれか 1 色で塗られている.

図: JOI 国の図 (H = 3, W = 4 の場合).図の上が北,左が西に対応する.

横断幕はこれらの柱を支柱としてかけることができる.ただし,横断幕が道路でないところを通ってい ると邪魔になってしまう.そこで,交差点に立っているこれらの柱のうち,「各辺がいずれかの道路と平行 であるような長方形」の 4 頂点となっているような異なる 4 本の柱を選び,その周囲に横断幕をかける.さ らに,このとき選ぶ 4 本の柱に黒色の柱・灰色の柱・白色の柱がそれぞれ 1 つ以上含まれているようにし たい.

このような 4 本の柱の選び方は何通りあるだろうか.

H, W と,JOI 国に立っている柱の色の情報が与えられたとき,4 本の柱の選び方の数を出力するプログ ラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 H, W が空白を区切りとして書かれている.
• 続く H 行には,JOI 国の交差点に立っている柱の色の情報が書かれている.i + 1 行目 (1 ≤ i ≤ H) に は,0, 1, 2 いずれかの整数が W 個空白区切りで書かれている.i + 1 行目の j 番目に書かれている整 数が 0 なら,交差点 (i, j) に立っている柱が黒色であることを表し,同様に,書かれている整数が 1 なら灰色,2 なら白色であることを表す.

출력

標準出力に,4 本の柱の選び方の数を 1 行で出力せよ.

제한

• 2 ≤ H ≤ 400 東西に走る道路の本数
• 2 ≤ W ≤ 400 南北に走る道路の本数

힌트

この入力例では,4 本の柱の選び方として

• (1, 1),(2, 1), (2, 2),(1, 2)
• (1, 1),(2, 1), (2, 4),(1, 4)
• (1, 2),(2, 2), (2, 3),(1, 3)
• (1, 3),(2, 3), (2, 4),(1, 4)
• (1, 1),(3, 1), (3, 4),(1, 4)
• (1, 2),(3, 2), (3, 3),(1, 3)
• (1, 2),(3, 2), (3, 4),(1, 4)
• (1, 3),(3, 3), (3, 4),(1, 4)
• (2, 1),(3, 1), (3, 2),(2, 2)
• (2, 1),(3, 1), (3, 3),(2, 3)
• (2, 2),(3, 2), (3, 4),(2, 4)
• (2, 3),(3, 3), (3, 4),(2, 4)

の 12 通りが存在するので 12 を出力する.