Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT122B - Tô màu các bảng hình chữ nhật

Công ty CE đã xây dựng một máy tô màu tự động (APM) để tô màu hoàn toàn một bảng bao phủ bởi các hình chữ nhật liền kề mà không chồng chéo lên nhau. Các hình chữ nhật này có thể có các kích thước khác nhau nhưng có màu cần tô được xác định trước.

Để tô màu bảng, APM có quyền lấy các bộ chổi với các màu khác nhau riêng biệt. APM lấy một chổi với màu C và tô tất cả các hình chữ nhật có màu C nhưng phải tuân thủ quy tắc: Một hình chữ nhật chỉ có thể được sơn nếu các hình chữ nhật ngay trên nó đã được sơn. Ví dụ như trong hình trên: Hình chữ nhật F chỉ có thể tô màu nếu hình chữ nhật C và D đã được tô màu. Chú ý: Khi tô màu một hình chữ nhật sẽ tô toàn bộ diện tích của hình chữ nhật, không được để trống lại.

Bạn đang viết chương trình cho APM để tô màu bảng đã cho sao cho số lần lấy chổi là tối thiểu. Chú ý: Nếu một chổi được lấy nhiều lần, thì tất cả các lần lấy sẽ được đếm.

Input

- Dòng đầu tiên chứa một số nguyên là số bộ test M (1<=M<=10).

- Mỗi bộ test có dạng như sau: Dòng đầu chứa số nguyên N, là số các hình chữ nhật. Sau đó là N dòng,  mỗi dòng gồm 5 số nguyên cách nhau bới dấu cách – đại diện cho một hình chữ nhật R - có ý nghĩa lần lượt là: y và x – tọa độ góc trên bên trái của R, tiếp y và x – tọa độ góc dưới bên phải của R, tiếp theo là mã màu của R.

- Chú ý:

  • Mà màu là một số nguyên trong phạm vi 1..20
  • Góc trên bên trái của bảng luôn có tọa độ (0,0)
  • Các tọa độ trong phạm vi 0..99
  • N nằm trong phạm vi 1..15

Output

Mỗi bộ test in trên một dòng số lần phải lấy chổi ít nhất có thể để tô màu

Example

Input:

1

7

0 0 2 2 1

0 2 1 6 2

2 0 4 2 1

1 2 4 4 2

1 4 3 6 1

4 0 6 4 1

3 4 6 6 2 Output: 3

Được gửi lên bởi:adm
Ngày:2012-02-24
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2024-06-24 16:25:25
De kho qua, ai ac chua huhu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.