trang chủ / bài tập / cornerchk

Kiểm tra hình chữ nhật góc

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.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 1,00một phần

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

Python 35.0s

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig