딸기 농사 1秒 128MB
問題
영기는 딸기 농사를 지으려고 한다.
하지만 어느 땅이 좋은지 구분하기가 힘든 상황이다.
따라서 영기의 방식으로 땅을 평가하여 점수를 얻기로 했다.
땅은 N행 M열 격자판으로 이루어져 있으며, 점수를 얻는 방식은 다음과 같다.
격자 지점에 대해 그 지점을 포함하여 만들 수 있는 직사각형의 경우의 수를 구한다.
이러한 작업을 모든 지점에서 한 다음 각 지점에서 얻은 점수를 전부 합하면 된다.
단, 직사각형 내부에 잡초 지점이 있으면 안되며, 직사각형 내부는 전부 농사를 지을 수 있는 지점이어야 한다.
땅의 표기는 '.'가 농사를 지을 수 있는 지점이며, '#'가 잡초 지점이다.
땅 정보가 주어졌을 때, 영기의 방식으로 얻은 점수를 출력하시오.
入力
첫 줄에 양의 정수 N과 M(1 ≤ N, M ≤ 2000)이 주어진다.
다음 N 줄에는 M개의 문자가 나타난다.
농사를 지을 수 있는 지점을 나타내는 '.', 잡초 지점을 나타내는 '#'
出力
땅의 점수를 출력한다.
例題 #1
2 3
.#.
..#
8
각 지점의 점수는 다음과 같다.
2 0 1
3 2 0
例題 #2
3 3
...
...
...
100
例題 #3
3 4
..#.
#...
...#
40
ログインしないとコードを書けません。