问题是找到一个单词在给定的N x N个字母矩阵中出现的次数。我们可以从任何一个单元移动到其他相邻的单元。第一行具有一个整数N,然后具有N x N矩阵。下一行具有M(字的大小),然后是要在矩阵中找到的字符串。
INPUT -
4
ABCD
ABCD
ABCD
ABCD
2
BC
OUTPUT -
10
我已经为相同的代码编写了以下代码,并使用递归来解决问题。函数adj使用其索引检查字符在矩阵中是否与前一个字符相邻。每当字符串完成时,功能检查都会增加计数。 2维数组会检查已访问和未访问的元素。
我得到的输出为
OUPUT
1
编辑:此输出仅是由于调试print语句,因此if语句仅被访问一次。这并不意味着在多次递归调用之后count变量为1。代码
#include <stdio.h>
int vis[500][500], count;
int adj(int a, int b, int c, int d) {
if((c == a - 1) && (d == b - 1)) {
return 1;
}
else if((c == a - 1) && (d == b)) {
return 1;
}
else if((c == a) && (d == b - 1)) {
return 1;
}
else if((c == a - 1) && (d == b + 1)) {
return 1;
}
else if((c == a + 1) && (d == b)) {
return 1;
}
else if((c == a + 1) && (d == b + 1)) {
return 1;
}
else if((c == a) && (d == b + 1)) {
return 1;
}
else if((c == a + 1) && (d == b - 1)) {
return 1;
}
else {
return 0;
}
}
void check(char grid[][500],int i, int j, int id, char word[], int n, int m) {
if(id == m) {
count++;
printf("%d\n", count); // just to debug
}
else {
for(int p = 0; p < n; p++) {
for(int q = 0;q < n; q++) {
if((grid[p][q] == word[id]) && (adj(i, j, p, q)) && (vis[p][q] != 1)) {
vis[p][q] = 1;
check(grid, p, q, id + 1, word, n, m);
vis[p][q] = 0;
}
}
}
}
}
int main() {
int n, m, id = 0;
char blank;
scanf("%d", &n);
scanf("%c", &blank);
char grid[n][n+1];
for(int i = 0; i < n; i++) {
scanf("%s", grid[i]);
grid[i][n] = '\0';
}
scanf("%d", &m);
char word[m+1];
scanf("%s", &word);
for(int i = 0; i < n; i++) {
for(int j = 0;j < n; j++) {
if(grid[i][j] == word[id]) {
vis[i][j] = 1;
check(grid, i, j, id + 1, word, n, m);
vis[i][j] = 0;
}
}
}
printf("%d\n", count);
return 0;
}
尝试更改此内容:
scanf("%s", &word);
对此:
scanf("%s", word);
因为word
是字符数组。