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

Sau kì thi VOI căng thẳng, Misaki quyết định thư giãn bằng cách chơi trò chơi tìm chữ. 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 được tạo thành bằng 1 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.

Ban đầu, các chữ cái trên bảng rất dễ tìm. Nhưng sau đó độ khó của game tăng lên, kích thước của bảng, số lượng chữ lớn hơn ban đầu rất nhiều, Misaki không thể tìm hết các chữ. Bạn hãy viết chương trình giúp Misaki tìm các chữ chưa tìm được nhé! wink

Yêu cầu: Cho bảng chữ cái NxM và Q chữ cần tìm, bạn hãy tìm vị trí chữ cái đầu tiên của dãy có cách nối tạo thành chữ đó.

Dữ liệu vào:

  - Dòng đầu chứa 3 số nguyên N,M,Q (1 ≤ N,M ≤ 200 | 1 ≤ Q ≤ 1000).

  - 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 chứa một chữ 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, mỗi dòng chứa 3 số nguyên u,v,d lần lượt là số dòng, số cột và cách nối tương ứng với cách đánh số ở đề bài. Nếu có nhiều vị trí thỏa yêu cầu, in ra vị trí có số dòng nhỏ nhất. Nếu có nhiều vị trí trên dòng thỏa yêu cầu, in ra vị trí có số cột nhỏ nhất. Nếu vẫn còn nhiều cách nối ở 1 ô, in ra cách nối có số thứ tự nhỏ nhất. Nếu không tìm được vị trí thỏa yêu cầu thì in ra -1.

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
    nawdawdh
    dtasoyjl
    hauzjhvn
    nwqcktyv
    twdaodur
    tixdfdjm
    ytopjvef
    azxgbmhr

    ntucoder
    dhnt
    abcd
    output
    1 1 3
    2 1 2
    -1
Back to Top