Tìm từ

Nguồn: tham khảo MarisaOJ, có chỉnh sửa (CLUE OJ – Chương 11: Mảng 2 chiều) Độ khó: Dễ Mảng 2 chiều Xâu

Đề bài

Cho một bảng $n \times m$ gồm các chữ cái. Có $q$ xâu $s$ cần tìm, với từng xâu $s$ hãy kiểm tra xem xâu có tồn tại trong bảng không. Từ được cho là tồn tại trong bảng nếu nó được ghép bởi các ký tự liên tiếp cùng nằm trên một hàng hoặc một cột, nhưng không được cả hai.

Xét bảng sau:

abc
def
ghi

Trong bảng này:

• Từ abc nằm trên dòng đầu tiên khi đọc từ trái qua phải.
• Từ cb nằm trên dòng đầu tiên khi đọc từ phải qua trái.
• Từ ad nằm trên cột đầu tiên khi đọc từ trên xuống dưới.
• Từ bcf không nằm trên bảng, vì muốn có được từ bcf, ta phải di chuyển trên cả hàng và cột.
• Từ he nằm trên cột thứ hai khi đọc từ dưới lên trên.
• Từ eb nằm trên cột thứ hai khi đọc từ dưới lên trên.

Dữ liệu nhập:

• Dòng đầu tiên gồm hai số nguyên $n, m$ – ma trận có $n$ dòng, $m$ cột.
• $n$ dòng tiếp theo, mỗi dòng có $m$ chữ cái.
• Dòng tiếp theo là số nguyên $q$ – số xâu cần tìm.
• $q$ dòng tiếp theo, mỗi dòng là một xâu $s$ cần tìm.

Dữ liệu xuất: gồm $q$ dòng, mỗi dòng in ra YES nếu từ có tồn tại, ngược lại in ra NO.

Điều kiện: $1 \le n, m, q, \text{length}(s) \le 50$.

Giải thích ví dụ: marisa có trên cột đầu tiên từ trên xuống; sama có trên cột cuối cùng từ dòng 2 trở xuống; laptrinh không tìm thấy; ira có ở dòng thứ hai từ phải qua trái; ama có ở cột cuối cùng từ dưới lên trên.

Ví dụ – input

6 4
mari
aris
risa
isam
sama
amar
5
marisa
sama
laptrinh
ira
ama

Ví dụ – output

YES
YES
NO
YES
YES

Lời mở đầu

Đây là trò "tìm chữ" quen thuộc trên báo giấy, nhưng dễ hơn một chút: từ chỉ được nằm thẳng trên một hàng hoặc một cột (không có đường chéo, không được bẻ góc). Bài giúp các bạn luyện hai kỹ năng: duyệt theo hướng trên mảng 2 chiều (giống bài Caro) và tìm xâu con. Mình giải bằng 2 cách và chạy cả hai trên bộ test thật – có một điều thú vị: cùng một ý tưởng vét cạn, bản C++ qua hết nhưng bản Python lại bị quá thời gian.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngmọi ô × 4 hướngCách 1vét cạnCách 2tìm xâu conLỗi saichỉ đọc xuôi

Bộ testBộ test chính thức có gì?

Nhóm	Các test	$n \times m$	$q$	Độ dài $s$ lớn nhất	Tỉ lệ YES	Cách 1 C++	Cách 1 Python	Cách 2
Nhỏ	1 – 30	5…10 × 5…10	5 … 10	9	155/220	30/30	30/30	30/30
Lớn	31 – 100	đúng 50 × 50	10 … 49	51	1430/2018	70/70	TLE nhiều test	70/70

Đề không chia subtask, nhưng bộ test tách rõ 2 nhóm: 30 test nhỏ (bảng tối đa $10 \times 10$) và 70 test lớn đều là bảng $50 \times 50$. Vài điều mình để ý:

• Bảng dùng cả chữ hoa và chữ thường (ở test lớn có đủ 52 loại chữ), và đáp án phân biệt hoa/thường – so sánh ký tự trực tiếp là đúng, đừng đổi hết về chữ thường.
• Có 186 truy vấn chỉ 1 ký tự – chỉ cần chữ đó có trong bảng.
• Có 1 truy vấn dài 51 ký tự (vượt giới hạn 50 của đề một chút, ở test 73) – dài hơn mọi hàng/cột nên đáp án là NO; code phải không bị truy cập ngoài mảng ở trường hợp này.
• Tổng cộng 2238 truy vấn, 1585 câu trả lời YES (khoảng 70%).

Ý tưởngMỗi ô là một điểm xuất phát, thử 4 hướng

Nếu xâu $s$ có trong bảng thì chữ $s_0$ nằm ở một ô $(i, j)$ nào đó, và các chữ tiếp theo $s_1, s_2, \dots$ nằm liên tiếp theo một trong 4 hướng: sang phải, sang trái, xuống dưới, lên trên. Vì vậy:

Thuật toán vét cạn

Với mỗi ô $(i, j)$ và mỗi hướng $(dx, dy)$, kiểm tra các ô $(i + k \cdot dx,\ j + k \cdot dy)$ với $k = 0, 1, \dots, |s| - 1$: tất cả phải nằm trong bảng và chữ ở đó phải bằng $s_k$. Chỉ cần một bộ (ô, hướng) thoả mãn là in YES.

Khác với bài Caro, ở đây phải thử đủ 4 hướng chứ không chỉ 2, vì từ có thể đọc ngược (phải qua trái, dưới lên trên): he chỉ đọc được từ dưới lên. Còn "không được cả hai" nghĩa là trên một lần đọc thì hướng không đổi – vòng lặp $k$ luôn đi theo một hướng cố định nên điều kiện này tự thoả.

Em nhập bảng và từ cần tìm rồi bấm Tiếp để xem máy thử từng ô có chữ cái đầu khớp và từng hướng (để gọn, các ô có chữ đầu không khớp mình bỏ qua):

Bảng (mỗi dòng cách nhau dấu cách) Từ cần tìm

Ví dụ nhanh:

Cách 1Vét cạn: mọi ô × 4 hướng

Hàm khop(s, i, j, d) kiểm tra xâu s có đọc được bắt đầu tại ô (i, j) theo hướng d không. Hàm main thử mọi ô, mọi hướng; biến co dùng để dừng sớm ngay khi tìm thấy.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi ô xuất phát và 4 hướng, hàm khop so từng ký tự.

Dữ liệu vào (stdin) – sửa thoải mái3 3 abc def ghi 6 abc cb ad bcf he eb

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để gọn, mình không dừng ở từng lần kiểm tra điều kiện của 3 vòng for lồng nhau; với ô có chữ đầu không khớp, 4 lần gọi khop được gộp thành 1 bước.

1. Điều kiện ra ngoài bảng được kiểm tra trước g[x][y] != s[k] (ngắt mạch ||), giống bài Caro.
2. Hàm khop trả về false ngay khi gặp ký tự sai đầu tiên, nên thực tế phần lớn các lần gọi chỉ so 1 ký tự (chữ đầu không khớp).
3. Xâu có 1 ký tự: chỉ cần chữ đó xuất hiện trong bảng là YES (bộ test có 186 truy vấn như vậy).

Không gian$O(n \cdot m)$

Thời gian$O(q \cdot n \cdot m \cdot 4 \cdot |s|)$ – tối đa khoảng $2.5 \cdot 10^7$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.08 giây. Bản Python cùng ý tưởng đúng hết 30 test nhỏ nhưng quá thời gian 1 giây ở nhiều test 50 × 50 (máy mình chấm 2 lần được 84/100 và 62/100, chậm nhất gần 2 giây) – Python chạy vòng lặp lồng nhau chậm hơn C++ hàng chục lần.

Cách 2Gom các hàng, cột (và bản đọc ngược) rồi tìm xâu con

Đổi góc nhìn: một từ "nằm trên hàng $i$ đọc từ trái qua phải" chính là một xâu con liên tiếp của xâu hàng $i$. Vậy mình gom sẵn tất cả các "dòng chữ" có thể đọc được:

• $n$ xâu hàng (đọc trái → phải) và $m$ xâu cột (đọc trên → dưới);
• đảo ngược cả $n + m$ xâu đó để có thêm các hướng phải → trái và dưới → trên.

Tổng cộng $2(n + m)$ xâu. Với mỗi truy vấn, chỉ cần hỏi "$s$ có là xâu con của xâu nào trong danh sách không" – C++ có sẵn x.find(s), Python có s in x.

C++▶ Chạy tay từng dòng codeCách 2: gom 2(n + m) dòng chữ (hàng, cột và bản đọc ngược) rồi dùng find.

Dữ liệu vào (stdin) – sửa thoải mái3 3 abc def ghi 6 abc cb ad bcf he eb

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi bước ở dòng find là một lần xét một xâu x trong ds; vùng tô xanh là chỗ tìm thấy s.

1. x.find(s) trả về vị trí đầu tiên của s trong x, hoặc string::npos nếu không có.
2. Vòng đảo ngược dùng sz = ds.size() lưu trước, vì trong lúc lặp mình push_back thêm vào ds – nếu viết t < ds.size() thì vòng lặp sẽ không bao giờ dừng.
3. Xâu dài hơn mọi hàng/cột (bộ test có 1 truy vấn dài 51 ký tự) thì find tự trả về không tìm thấy.

Không gian$O(n \cdot m)$

Thời gian$O(q \cdot 2(n + m) \cdot \max(n, m) \cdot |s|)$ – trên thực tế rất nhanh

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.04 giây; bản Python đúng 100/100 test, chậm nhất 0.29 giây – nhờ phép in được cài đặt bên trong bằng C nên rất nhanh.

Lỗi hay gặpChỉ đọc xuôi

Chỉ thử 2 hướng (phải và xuống): đúng 10/100 test

Nhiều bạn quen bài Caro nên chỉ thử hướng sang phải và xuống dưới. Mình sửa vòng d thành d += 2 (chỉ còn hướng phải, xuống) và chấm lại: chỉ đúng 10/100 test, vì gần như test nào cũng có từ đọc ngược như ira, ama trong ví dụ.

Ghi chú của mình: Cách 1 (C++) và Cách 2 (C++ và Python) đều đạt 100/100 test. Bản Python của Cách 1 bị quá thời gian ở nhóm test $50 \times 50$, nên nếu viết Python thì các bạn nên dùng Cách 2. Bản chỉ đọc xuôi được 10/100 test.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇