Bài 2: (Tên file chương trình: DANDEN.PAS)
Cho một lưới tọa độ nguyên, hoành độ từ 1 đến M, tung độ từ 1 đến N (M,N <=100). Trên K nút cho trước của lưới, mỗi nút cần đặt một đèn màu sao cho hai đèn ở hai nút có cùng hoành độ hoặc có cùng tung độ phải có màu khác nhau. Hãy tìm một cách bố trí dàn đèn sao cho số màu phải dùng là ít nhất. Các màu đã được sử dụng phải được đánh số bởi các số nguyên dương liên tục bắt đầu từ 1.
Dữ liệu: vào file văn bản DANDEN.INP
- Dòng đầu ghi 3 số M, N, K
- Dòng thứ i trong số K dòng tiếp theo ghi hoành độ và tung độ của nút thứ i trong dãy K nút cần đặt đèn (i = 1, 2, ..., k).
Kết quả: ghi ra file văn bản DANDEN.OUT
- Dòng đầu ghi số P, biểu diễn số lượng màu cần phải sử dụng
- Dòng thứ i trong số K dòng tiếp theo ghi màu của đèn nút thứ i (i = 1, 2, ..., k).
Ví dụ:
DANDEN.INP
4 5 13
1 1
1 2
1 5
3 1
4 1
3 2
2 3
3 3
4 3
2 4
4 4
2 5
4 5
DANDEN.OUT
4
4
3
2
3
2
4
4
2
3
3
1
1
4
## M.n giúp e vs..ns rõ giúp e cái thuật toán và cả code nữa ạ..tks trc
Cho một lưới tọa độ nguyên, hoành độ từ 1 đến M, tung độ từ 1 đến N (M,N <=100). Trên K nút cho trước của lưới, mỗi nút cần đặt một đèn màu sao cho hai đèn ở hai nút có cùng hoành độ hoặc có cùng tung độ phải có màu khác nhau. Hãy tìm một cách bố trí dàn đèn sao cho số màu phải dùng là ít nhất. Các màu đã được sử dụng phải được đánh số bởi các số nguyên dương liên tục bắt đầu từ 1.
Dữ liệu: vào file văn bản DANDEN.INP
- Dòng đầu ghi 3 số M, N, K
- Dòng thứ i trong số K dòng tiếp theo ghi hoành độ và tung độ của nút thứ i trong dãy K nút cần đặt đèn (i = 1, 2, ..., k).
Kết quả: ghi ra file văn bản DANDEN.OUT
- Dòng đầu ghi số P, biểu diễn số lượng màu cần phải sử dụng
- Dòng thứ i trong số K dòng tiếp theo ghi màu của đèn nút thứ i (i = 1, 2, ..., k).
Ví dụ:
DANDEN.INP
4 5 13
1 1
1 2
1 5
3 1
4 1
3 2
2 3
3 3
4 3
2 4
4 4
2 5
4 5
DANDEN.OUT
4
4
3
2
3
2
4
4
2
3
3
1
1
4
## M.n giúp e vs..ns rõ giúp e cái thuật toán và cả code nữa ạ..tks trc
