30/09/2018, 18:30

Cần giúp đỡ giải thích ý tưởng xuất ma trận hình xoắn ốc và tìm kiếm theo đường zí zắc

ai giải thích cho em hiểu ý tưởng xuất ma trận hình xoắn ốc và tìm kiếm theo đường zí zắt đc không

明玉 viết 20:40 ngày 30/09/2018

Theo mình thì dễ nhất là lập bộ luật/quy tắc dò đường trong ma trận đúng với đề bài - kiểu như đầu tiên thì duyệt trái sang phải, đụng tường thì đổi hướng rồi dò tiếp cho đến khi nào hết ô trống. Dùng vòng lặp kết hợp if else kiểm tra trạng thái từng ô trống.
Ví dụ quy tắc đi theo đường xoắn ốc:

  • Bắt đầu từ ô trống ở góc trên-trái, hướng đi là hướng Đông.
  • Đụng tường hoặc ô đã duyệt rồi thì bẻ hướng 90 độ theo kim đồng hồ rồi duyệt tiếp.
  • Lặp lại bước trên cho đến khi hết ô trống.
    Bài zigzag cũng tương tự thôi, quy tắc sẽ nhiều hơn nhưng ý tưởng không đổi (đi theo đường chéo, đụng tường quay 180 độ…) . Còn muốn code cực ngắn thì phải nghiên cứu toán học .
trun viết 20:31 ngày 30/09/2018

zít zắt coi bộ cay quá bạn ơi

明玉 viết 20:43 ngày 30/09/2018

Ví dụ Bộ quy tắc zigzag:

Khởi tạo (tùy đề bài của bạn):

  • Xuất phát từ ô phía trên + bên trái;
  • Hướng đầu tiên là hướng Đông Bắc;
  • Các hướng sẽ sử dụng: Đông Bắc, Tây Nam, Đông, Nam;
  • Sau đó duyệt theo hướng đã định.

Hướng Đông Bắc:

  • Nếu không thể đi tiếp được do không còn ô (theo hướng hiện hành) để mà đi thì rơi vào 3 trường hợp:
  • Nếu Hướng Đông đi được (do có ô) thì đổi sang Hướng Đông;
  • Không thì Nếu Hướng Nam đi được thì đổi sang Hướng Nam;
  • Không đi được cả 2 hướng trên thì kết thúc.

Hướng Tây Nam

  • Nếu không thể đi tiếp được do không có ô để đi thì 3 trường hợp:
  • Nếu Hướng Nam đi được thì đổi sang Hướng Nam;
  • Không thì Nếu Hướng Đông đi được thì đổi sang Hướng Đông;
  • Không đi được cả 2 hướng trên thì kết thúc;

Hướng Đông

  • Đi được 1 ô thì 2 trường hợp:
  • Nếu Hướng Tây Nam đi được thì đổi sang Hướng Tây Nam;
  • Không thì đổi sang hướng Đông Bắc;

Hướng Nam

  • Đi được 1 ô thì 2 trường hợp:
  • Nếu Hướng Đông Bắc đi được thì đổi sang Hướng Đông Bắc;
  • Không thì đổi sang hướng Tây Nam;

Còn đây là code mẫu trên mạng, ý tưởng như mình thôi, nhưng họ dùng nhiều biến trạng thái nên code vẫn khá là gọn http://rosettacode.org/wiki/Zig-zag_matrix

Bài liên quan
0