Đếm hình chữ nhật góc

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới $n \times n$ ô vuông, mỗi ô được tô màu đen hoặc trắng (ô đen = 1, ô trắng = 0).

Một hình chữ nhật góc (corner subgrid) là tập hợp 4 ô tạo thành 4 góc của một hình chữ nhật $r \times c$ ( $r, c \geq 2$ ), tức là 4 ô tại vị trí $(r_{1}, c_{1})$ , $(r_{1}, c_{2})$ , $(r_{2}, c_{1})$ , $(r_{2}, c_{2})$ với $r_{1} < r_{2}$ và $c_{1} < c_{2}$ , và cả 4 ô đều có màu đen.

Hãy đếm số lượng hình chữ nhật góc trong lưới.

Dữ liệu vào

Dòng đầu: số nguyên $n$ ( $1 \leq n \leq 3000$ ).
$n$ dòng tiếp theo: mỗi dòng là một xâu nhị phân độ dài $n$ mô tả một hàng của lưới.

Dữ liệu ra

In ra số lượng hình chữ nhật góc.

Ràng buộc

$1 \leq n \leq 3000$

Ví dụ

Input	Output	Giải thích
5 10001 11101 11001 10111 01001	12	Có 12 bộ 4 góc tạo thành hình chữ nhật với cả 4 góc đều là ô đen.
10 0011011011 1010001000 1000100000 1111011001 0000110101 0001011100 1001011000 1000101010 1000110111 0101010011	77

Bình luận

Không có bình luận tại thời điểm này.