다음 문제는 일간 신문 십자말 풀이의 예입니다. 여기에 2차원 문자 배열이 제공되며 문제는 2차원 문자 배열 미로에서 주어진 단어를 찾는 것입니다. 검색 알고리즘에는 다음에서 개별 문자를 찾는 것이 포함됩니다. 위에서 아래로 ,오른쪽에서 왼쪽 대각선이 아닌 반대의 경우도 마찬가지입니다.
예를 들어 이해하자
입력- 문자열 단어-LAYS
2D 문자열[ ] - { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };
출력- 2D 문자 배열에서 주어진 문자열의 개수:7
설명 - 단어의 문자열 배열이 주어지고 그 중에서 Top-Bottom, Right-Left, Bottom-Top 및 Left-Right와 같은 모든 방향으로 검색할 수 있는 "LAYS"라는 단어를 찾아야 합니다. 코드의 카운터 플래그는 주어진 검색 문자열이 발견될 때마다 합산되고 결과에 대해 마지막에 카운트가 반환됩니다. 예에서 우리는 LAYS가 7번 형성되는 것을 볼 수 있습니다. 즉,
1->L 오아 P예 -LAYS-> 왼쪽에서 오른쪽으로
2 ->S 아야 오엘 -LAYS(오른쪽에서 왼쪽으로)
3->레이스 T-LAYS(왼쪽에서 오른쪽으로)
4->ML VAYS- LAYS(왼쪽에서 오른쪽으로)
5->레이사 A-LAYS(왼쪽에서 오른쪽으로)
6->LA OYLS -LAYS(왼쪽에서 오른쪽으로)
7->(아래에서 위로) Red LAYS
입력- 문자열 단어 - CAMP
2D 문자열[ ] - { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }
출력- 2D 문자 배열에서 주어진 문자열의 개수:0
설명-: 단어의 문자열 배열이 주어지고 그 중에서 Top-Bottom, Right-Left, Bottom-Top 및 Left-Right와 같은 모든 방향으로 검색할 수 있는 "LAYS"라는 단어를 찾아야 합니다. 코드의 카운터 플래그는 주어진 검색 문자열이 발견될 때마다 합산되고 결과에 대해 마지막에 카운트가 반환됩니다. 예에서 우리는 BOOK이 0 으로 형성된 것을 볼 수 있습니다. 타임스.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 추가 처리를 위해 일부 유틸리티 변수와 함께 findString()에 전달되는 String(word) 및 String 배열이 제공됩니다.
- 행렬의 문자가 순회되고 문자열을 시작하기 위해 문자가 선택됩니다.
- 선택된 문자에 대해 알고리즘에 따라 가능한 모든 방향으로 재귀적으로 주어진 문자열을 찾습니다.
- 일치하는 항목이 발견되면 카운터가 증가합니다.
- 첫 번째 시작 문자가 끝나면 다음 문자에 대해 프로세스가 반복됩니다.
- 카운트 합계는 해당 일치 항목으로 계산됩니다.
- 최종 답변이 캡처되고 결과가 인쇄됩니다.
예시
#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;
} 위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
출력
Count of number of given string in 2D character array: 6