Ghép bản đồ
Đề bài
Mô tả
Ảnh chụp từ máy bay hoặc vệ tinh của một vùng cần lập bản đồ thường có độ phân giải đủ cao để nhận ra duy nhất các đặc điểm địa hình chính. Vì mỗi bức ảnh chỉ bao quát được một phần nhỏ của trái đất, để lập bản đồ của vùng lớn hơn người ta chụp nhiều vùng nhỏ chồng lên nhau, rồi ghép chúng lại thành bản đồ của vùng lớn.
Trong bài này bạn được cho một số bản đồ của các vùng hình chữ nhật, mỗi bản đồ là một bảng các ô, mỗi ô là một ký tự. Một ô chứa một chữ cái in hoa (A đến Z) nếu vùng tương ứng có một đặc điểm chính nhận dạng được. Các chữ cái khác nhau ứng với các đặc điểm khác nhau, nhưng cùng một đặc điểm (chẳng hạn một con đường) có thể xuất hiện ở nhiều ô. Một ô chứa dấu gạch nối (-) nếu vùng đó không có đặc điểm nào nhận dạng được.
Ghép hai bản đồ nghĩa là đặt chồng chúng lên nhau sao cho một hoặc nhiều đặc điểm chung trùng nhau. Một ô có đặc điểm của bản đồ này có thể được đặt chồng lên một ô không có đặc điểm của bản đồ kia. Tuy nhiên, hai đặc điểm khác nhau (hai chữ cái khác nhau) không được nằm chồng lên cùng một ô.
Xét năm bản đồ cùng có hàng, cột dưới đây (theo thứ tự là bản đồ , , , , ):
Bản đồ :
grid - - A - C - - - - D - - - - B
Bản đồ :
grid C - - - - D - - - F B - - - -
Bản đồ :
grid C - - - - - - - - - B - A - C
Bản đồ :
grid - - - - D - E - - B - - - - -
Bản đồ :
grid - D - - C - - - - G - - - - B
Cột cuối của bản đồ khớp hoàn toàn với cột đầu của bản đồ , nên hai bản đồ này có thể chồng lên nhau để được một bản đồ hàng, cột. Bản đồ cũng có thể chồng lên bản đồ , vì các đặc điểm C và B ở cột cuối của bản đồ trùng với các đặc điểm ở cột đầu của bản đồ ; chữ D không khớp với ô - ở giữa cột nhưng không gây xung đột. Tương tự, hàng đầu của bản đồ cũng có thể chồng lên hàng cuối của bản đồ .
Điểm của một cách chồng hai bản đồ là số ô mà ở đó đặc điểm của hai bản đồ trùng nhau (hai ô chồng lên nhau chứa cùng một chữ cái). Điểm của một cặp bản đồ là điểm lớn nhất trong mọi cách chồng hợp lệ của chúng. Như vậy điểm của một cặp bản đồ cùng có hàng, cột nằm trong đoạn từ đến .
Một độ lệch là cặp số nguyên xác định cách chồng bản đồ lên bản đồ : ô ở hàng , cột của nằm chồng lên ô ở hàng , cột của ( là độ lệch hàng, là độ lệch cột của so với ). Ví dụ, cách chồng bản đồ và bản đồ nói trên có độ lệch và điểm . Hai cách chồng bản đồ và bản đồ cho điểm có độ lệch và . Khi xét một cặp bản đồ, luôn là bản đồ có số thứ tự nhỏ hơn, là bản đồ có số thứ tự lớn hơn.
Ghép hai bản đồ cho bản đồ mới là hình chữ nhật nhỏ nhất bao cả hai bản đồ đã chồng; mỗi ô của nó chứa chữ cái nếu một trong hai bản đồ có chữ cái ở ô đó, ngược lại chứa -.
Các bước ghép một dãy bản đồ như sau:
- Ghép cặp bản đồ trong dãy có điểm dương lớn nhất. Nếu nhiều cặp cùng điểm, chọn cặp chứa bản đồ có số thứ tự nhỏ nhất; nếu vẫn còn nhiều cặp, chọn cặp có bản đồ còn lại có số thứ tự nhỏ nhất.
- Xoá hai bản đồ vừa ghép khỏi dãy.
- Thêm bản đồ mới vào dãy, với số thứ tự là số lớn hơn liền sau số thứ tự lớn nhất đã dùng.
Trong ví dụ trên, bản đồ và được ghép thành bản đồ , và bản đồ , bị xoá khỏi dãy. Các bước , , được lặp lại cho đến khi dãy chỉ còn một bản đồ, hoặc không còn cặp bản đồ nào ghép được (tức là mọi cặp đều có điểm ).
Nếu hai bản đồ có thể ghép theo nhiều cách cùng cho điểm lớn nhất, dùng cách có độ lệch hàng nhỏ nhất; nếu vẫn còn nhiều cách, dùng cách có độ lệch cột nhỏ nhất trong số đó.
Dữ liệu vào
Dữ liệu gồm một hoặc nhiều bộ test, mỗi bộ test gồm từ đến bản đồ. Mỗi bộ test bắt đầu bằng một số nguyên là số bản đồ trong dãy. Tiếp theo là các bản đồ theo thứ tự (bản đồ thứ có số thứ tự ), mỗi bản đồ bắt đầu bằng một dòng chứa hai số nguyên và () là số hàng và số cột của bản đồ, theo sau là dòng dữ liệu của bản đồ. ký tự đầu tiên của mỗi dòng này là dữ liệu bản đồ (mỗi ký tự là chữ cái in hoa hoặc -); các ký tự còn lại trên dòng (nếu có, có thể gồm cả dấu cách) phải được bỏ qua.
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in dòng Case k với là số thứ tự của bộ test (), sau đó là các bản đồ còn lại trong dãy theo thứ tự số thứ tự tăng dần. Mỗi bản đồ được in bằng một dòng MAP n: (ba dấu cách ở đầu, là số thứ tự của bản đồ), tiếp theo là bản đồ được bao bởi một khung: dòng đầu và dòng cuối là +, dấu -, + ( là số cột của bản đồ); mỗi hàng của bản đồ in thành một dòng |, hàng đó, |. Định dạng đúng như ví dụ.
Ràng buộc
- Mỗi bộ test có từ đến bản đồ, .
- Không bản đồ ghép nào có quá cột.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 5 --A-C ----D ----B 3 5 C---- D---F B---- 3 5 C---- ----- B-A-C 3 5 ----D -E--B ----- 3 5 -D--C ----G ----B 2 3 5 ----A ----B ----C 3 5 A---- B---- D---- 0 |
Case 1 MAP 9: +-------------+ |-D--C--------| |----G--------| |----B-A-C----| |--------D---F| |-----E--B----| |-------------| +-------------+ Case 2 MAP 1: +-----+ |----A| |----B| |----C| +-----+ MAP 2: +-----+ |A----| |B----| |D----| +-----+ |
Bộ test 1 là năm bản đồ ở trên: bản đồ và được ghép đầu tiên (điểm ) thành bản đồ , cuối cùng mọi bản đồ được ghép thành bản đồ . Bộ test 2: mọi cách chồng có hai chữ cái trùng nhau đều buộc C nằm chồng lên D (xung đột), nên hai bản đồ không ghép được. |
| 4 2 3 A-B --- 2 2 A- -- 1 3 B-A ignored 2 2 ZZ ZZ 0 |
Case 1 MAP 4: +--+ |ZZ| |ZZ| +--+ MAP 6: +-----+ |A-B-A| |-----| +-----+ |
Ví dụ tự thêm. Các cặp , , đều có điểm , cặp chứa bản đồ và bản đồ còn lại nhỏ nhất là : ghép thành bản đồ gồm hai hàng A-B, ---. Phần ignored sau ký tự đầu của bản đồ bị bỏ qua. Cặp có hai cách cho điểm với độ lệch của bản đồ so với bản đồ là và ; chọn nên được bản đồ . Bản đồ không ghép được với bản đồ nào. |
https://oj.chuyentin.pro/problem/icpcwf04_f
Bình luận