Bài toán dưới đây là một ví dụ về ô chữ nhật báo, ở đây chúng ta được cung cấp mảng ký tự 2 Chiều và câu lệnh bài toán là tìm ra từ đã cho từ mê cung mảng ký tự 2 Chiều. Từ trên đến dưới , Từ phải sang trái và ngược lại nhưng không theo đường chéo.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào- Chuỗi từ-LAYS
Chuỗi 2D [] - {"LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS"};
Đầu ra- Đếm số chuỗi đã cho trong mảng ký tự 2D:7
Giải thích - Vì chúng ta được cung cấp với mảng chuỗi các từ và từ chúng, chúng ta phải tìm từ "LAYS" có thể được tìm kiếm theo bất kỳ hướng nào như Trên-Dưới, Phải-Trái, Dưới-Trên và Trái-Phải. Cờ bộ đếm trong mã cộng lại mỗi khi tìm thấy chuỗi tìm kiếm đã cho và số lượng được trả về ở cuối cho kết quả. Trong ví dụ này, chúng ta có thể thấy LAYS được hình thành 7 lần, tức là
1-> L Ô A P YS -LAYS-> Trái sang phải
2 -> S Đ YA Ô L -LAYS (Phải sang trái)
3-> VÁCH NGĂN T-LAYS (Trái sang phải)
4-> M L V AYS- LAYS (Trái sang phải)
5-> LAYSA A-LAYS (Trái sang phải)
6-> LA O YLS -LAYS (Trái sang phải)
7 -> (Từ dưới lên trên) trong LAYS màu đỏ
Đầu vào- Chuỗi từ- TRẠI
Chuỗi 2D [] - {"BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL"}
Đầu ra- Đếm số chuỗi đã cho trong mảng ký tự 2D:0
Giải thích-: Vì chúng ta được cung cấp với mảng chuỗi các từ và từ chúng, chúng ta phải tìm từ "LAYS" có thể được tìm kiếm theo bất kỳ hướng nào như Trên-Dưới, Phải-Trái, Dưới-Trên và Trái-Phải. Cờ bộ đếm trong mã cộng lại mỗi khi tìm thấy chuỗi tìm kiếm đã cho và số lượng được trả về ở cuối cho kết quả. Trong ví dụ này, chúng ta có thể thấy SÁCH được hình thành 0 lần.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
- Chúng tôi được cung cấp với một mảng Chuỗi (từ) và Chuỗi cùng với một số biến tiện ích được chuyển vào findString () để xử lý thêm.
- Các ký tự trong ma trận sau đó được duyệt và một ký tự được chọn để bắt đầu chuỗi.
- Đối với ký tự đã được chọn, chúng tôi tìm thấy cho chuỗi đã cho một cách đệ quy theo tất cả các hướng có thể theo thuật toán
- Nếu tìm thấy kết quả khớp thì bộ đếm sẽ tăng lên
- Sau khi chúng ta hoàn thành với ký tự bắt đầu đầu tiên, quá trình này sẽ được lặp lại cho ký tự tiếp theo
- Tổng số sau đó được tính với các kết quả phù hợp tương ứng
- Câu trả lời cuối cùng sau đó được ghi lại và kết quả được in ra.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) {
int count = 0;
if (r >= 0 && r <= maxR && c >= 0) {
if (c <= maxC && word[index] == arr[r][c]) {
char res = word[index];
index = index + 1;
arr[r][c] = 0;
if (word[index] == 0) {
count = 1;
} else {
count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index);
count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index);
count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index);
count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index);
}
arr[r][c] = res;
}
}
return count;
}
int findString(string word, int r, int c, string str[], int countR, int countC) {
int count = 0;
for (int i = 0; i < countR; ++i) {
for (int j = 0; j < countC; ++j) {
count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0);
}
}
return count;
}
int main() {
string word = "FLOOD";
string inp[] = {"FPLIOKOD","FLOODYUT","YFLOODPU","FMLOSODT","FILPOYOD", FLOOOODE " };
string str[(sizeof(inp) / sizeof( * inp))];
for (int i = 0; i < (sizeof(inp) / sizeof( * inp)); ++i) {
str[i] = inp[i];
}
cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof( * inp)), str[0].size());
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of number of given string in 2D character array: 6