WORDFIND2 - Trò chơi tìm chữ 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: mrtan_lovelife

Sau khi chơi Trò chơi tìm chữ, Misaki đã sửa lại một tí về luật chơi để trò chơi đơn giản hơn. Cách chơi như sau: Cho bảng chữ cái kích thước NxM, cần tìm trên bảng Q dãy các chữ cái độ dài L được tạo thành bằng một trong các cách nối như sau:
  1. Nối các chữ cái nằm trên cùng 1 dòng.

  2. Nối các chữ cái nằm trên cùng 1 cột.

  3. Nối các chữ cái nằm trên đường chéo từ phía trên bên trái xuống phía dưới bên phải.

  4. Nối các chữ cái nằm trên đường chéo từ phía trên bên phải xuống phía dưới bên trái.

Thay đổi của trò chơi đó là bạn chỉ cần xác định xem có tồn tại ít nhất một cách nối  trên bảng tạo thành chữ cần tìm hay không. Bạn hãy viết chương trình trả lời câu hỏi đó nhé! wink

Yêu cầu: Cho bảng chữ cái NxM và Q chữ có độ dài L cần tìm, bạn hãy xác định xem có cách nối trên bảng tạo thành chữ đó hay không.

Dữ liệu vào:

  - Dòng đầu chứa 4 số nguyên N,M,Q,L (1 ≤ N,M ≤ 500 | 1 ≤ Q ≤ 105 | 1 ≤ L ≤ max(N,M)).

  - N dòng tiếp theo, mỗi dòng chứa M chữ cái, chữ cái aij là chữ cái ở hàng i và cột j của bảng.

  - Dòng thứ N+2 là dòng trống.

  - Q dòng tiếp theo, mỗi dòng chứa một chữ độ dài L là chữ cần tìm.

Dữ liệu ra: 

  Gồm Q dòng tương ứng với Q chữ cần tìm, nếu tìm tồn tại cách nối thì in ra 'YES', ngược lại in ra 'NO'.

Lưu ý: Các chữ cái sau khi nối sẽ được đọc từ trái qua phải (với cách nối 1,3,4) hoặc từ trên xuống dưới (với cách nối 2).

Ví dụ

  • input
    8 8 3 8
    nawdawdh
    htasoyjl
    aauzjhvn
    twqcktyv
    rwdaodur
    aixdfdjm
    ntopjvef
    gzxgbmhr

    ntucoder
    nhatrang
    lovelife
    output
    YES
    YES
    NO
Back to Top