TLEoj Contest #01 - Đếm hình vuông

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Bạn được cho một ma trận $m \times n$ ( $m$ hàng $n$ cột) gồm các số $0$ và $1$ . Bạn cần đếm số hình vuông có các đỉnh là các ô của ma trận, các cạnh là các hàng và cột của ma trận sao cho giá trị ở cả bốn đỉnh của hình vuông đều là $1$ (hay nói cách khác, bạn cần đếm số bộ $(i, j, k)$ $(1 \le i \le m, 1 \le j \le n, 0 \le k \le \min(m, n))$ sao cho giá trị các ô $(i, j), (i + k, j), (i, j + k), (i + k, j + k)$ đều là $1$ )

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên gồm các số nguyên dương $m, n$ $(m, n \le 2000)$
$m$ dòng tiếp theo, mỗi dòng gồm một chuỗi $n$ ký tự $0$ hoặc $1$ , ký tự thứ $i$ ở hàng thứ $j$ miêu tả giá trị của ô $(i, j)$ trong ma trận.

Output: (màn hình)

In ra một số nguyên duy nhất là số lượng hình vuông thỏa mãn.

Subtasks

Subtask 1 $(40\%)$ : $m, n \le 100$
Subtask 2 $(30\%)$ : $m, n \le 200$
Subtask 3 $(20\%)$ : $m, n \le 600$
Subtask 4 $(10\%)$ : Không có giới hạn gì thêm

Sample 1

Input (bàn phím)

Output (màn hình)

Notes

Mỗi ô của ma trận có giá trị $1$ đều là một hình vuông kích thước $1 \times 1$ .
Có một hình vuông kích thước $2 \times 2$ gồm các đỉnh $(2, 1), (2, 2), (3, 1), (3, 2)$

Bình luận

Không có bình luận nào.