Đề bài
Một cuốn sách đố vui đưa ra ba hình đầu tiên của một họ hình vẽ và đố bạn vẽ tiếp:
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCCTrước khi đọc tiếp, bạn hãy quan sát và thử tự gọi tên quy luật. Còn đây là phát biểu chính xác: hình thứ n là một hình vuông gồm 2n − 1 hàng, mỗi hàng dài 2n − 1 chữ cái, không có dấu cách. Đánh số hàng và cột từ 0, tâm nằm ở vị trí n − 1. Ô ở hàng r, cột c là chữ cái đứng sau A d vị trí trong bảng chữ cái, với d = max(|r − (n − 1)|, |c − (n − 1)|) là số vòng tính từ tâm ra đến ô đó. Như vậy tâm là A, vòng bao quanh tâm là B, và viền ngoài cùng là chữ cái thứ n.
Hãy viết decode_the_pattern(n).
Đầu vào
n: Thứ tự của hình cần dựng trong họ (tối đa 26, nên chữ cái không bao giờ vượt quá Z).
Đầu ra
Trả về 2n − 1 hàng theo thứ tự từ trên xuống. Khi n bằng 0, trả về danh sách rỗng.
Ràng buộc
0 ≤ n ≤ 26
Ví dụ
Đầu vào:
n = 2
Kết quả mong đợi:
expected = ["BBB", "BAB", "BBB"]
Đầu vào:
long long n = 2;
Kết quả mong đợi:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
Đầu vào:
long n = 2;
Kết quả mong đợi:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
Giải thích
Chỉ có tâm (1, 1) cách tâm 0 vòng, mọi ô khác cách 1 vòng: ["BBB", "BAB", "BBB"].
Đầu vào:
n = 4
Kết quả mong đợi:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
Đầu vào:
long long n = 4;
Kết quả mong đợi:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Đầu vào:
long n = 4;
Kết quả mong đợi:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Giải thích
Các ô ở viền cách tâm 3 vòng (D); hàng 3 là hàng giữa: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đánh dấu tâm của mỗi hình mẫu và xem các chữ cái thay đổi thế nào khi đi ra xa tâm.
Gợi ý 2
Các ô trên cùng một vòng có chung một chữ cái; số vòng là giá trị lớn hơn giữa khoảng cách theo hàng và khoảng cách theo cột đến tâm.
Gợi ý 3
Kiểm tra quy tắc của bạn trên hình mẫu n = 3 trước khi dựng với n bất kỳ.
Độ phức tạp mong đợi
thời gian O(n^2), bộ nhớ phụ O(n^2)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.