Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Tìm từ trong lưới chữ cái

    Cho một lưới chữ cái kích thước r×cr \times cr×c. Hãy kiểm tra xem từ WWW có thể được tạo thành bằng cách đi qua các ô kề nhau (theo phương ngang hoặc dọc) hay không.

    Quy tắc: bắt đầu từ một ô bất kỳ, mỗi bước di chuyển sang ô kề cạnh (lên/xuống/trái/phải), và mỗi ô chỉ được dùng tối đa một lần trong cùng một lần ghép.

    Ví dụ: với lưới

    ABCE
SFCS
ADEE

    từ ABCCED tồn tại nên kết quả là YES.

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên rrr và ccc. rrr dòng tiếp theo, mỗi dòng là một chuỗi gồm ccc chữ cái (lưới). Dòng cuối chứa từ cần tìm WWW.

    • Ràng buộc đầu vào:

      1≤r,c≤41 \le r, c \le 41≤r,c≤4; độ dài WWW trong khoảng [1,16][1, 16][1,16]; lưới và WWW chỉ gồm chữ cái in hoa.

    • Định dạng đầu ra:

      In YES nếu tìm được từ WWW trong lưới, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    3 4
ABCE
SFCS
ADEE
ABCCED

    Đầu ra:

    YES

    Giải thích:

    Đường đi A->B->C->C->E->D tồn tại nên in YES.

    Đang tải editor...