Kiểm tra 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 lưới $n \times n$ gồm các chữ cái viết hoa. Lưới chỉ sử dụng $k$ chữ cái đầu tiên trong bảng chữ cái ( $A$ , $B$ , ...).

Một hình chữ nhật con hợp lệ là một tập hợp 4 ô tại các góc $(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ới mỗi chữ cái trong số $k$ chữ cái, hãy xác định xem có tồn tại một hình chữ nhật con hợp lệ mà cả 4 góc đều là chữ cái đó hay không.

Dữ liệu vào

Dòng đầu gồm hai số nguyên $n$ và $k$ .

$n$ dòng tiếp theo, mỗi dòng gồm $n$ chữ cái mô tả lưới.

Dữ liệu ra

In ra $k$ dòng. Dòng thứ $i$ in YES nếu chữ cái thứ $i$ có hình chữ nhật con hợp lệ, ngược lại in NO.

Ràng buộc

$1 \leq n \leq 3000$
$1 \leq k \leq 26$

Ví dụ

Input	Output	Giải thích
4 5 AAAA CBBC CBBE AAAA	YES YES NO NO NO	A: hàng 0 và hàng 3 đều có A ở cột 0,1,2,3 → YES. B: hàng 1 và hàng 2 đều có B ở cột 1,2 → YES. C,D,E không có hình chữ nhật hợp lệ.
4 2 ABAB AABB BBBB BBBB	NO YES	A: hàng 0 có A ở cột {0,2}, hàng 1 có A ở cột {0,1}, chỉ chung 1 cột → NO. B: hàng 0 và hàng 2 đều có B ở cột 1 và 3 → YES.

Bình luận

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