Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Giải mã quy luật hình vẽ

Tìm ra quy luật của một họ hình vuông chữ cái từ vài hình đầu tiên, rồi dựng hình thứ n bất kỳ.

Bạn sẽ học được gì

  • Mô tả một hình vẽ bằng quy tắc theo số hàng và số cột
  • Tính số vòng bằng giá trị lớn nhất của hai khoảng cách
  • Ánh xạ một số thành chữ cái

Đề bài

Xem bản gốc (English)

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
                  CCCCC

Trướ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ụ

Ví dụ 1
Đầ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"].

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.