问题是找到一个单词在给定的N x N字母矩阵中出现的次数。我们可以从任何单元格移动到其他相邻单元格。第一行有一个整数 N，然后是一个 N x N 矩阵。下一行有 M(单词的大小(，然后在矩阵中找到一个字符串。
Input:
4
ABCD
ABCD
ABCD
ABCD
2
BC
Expected output:
10
我为此编写了以下代码，并使用递归来解决问题。函数 adj 使用其索引检查该字符在矩阵中是否与前一个字符相邻。每当字符串完成时，函数检查都会增加计数。二维数组检查已访问和未访问的元素。
我得到的输出为
OUPUT
1
编辑 1：此输出只是因为调试打印语句，因此 if 语句只被访问一次。这并不意味着在多次递归调用后计数变量为 1。
编辑2：scanf语句中不应该有&。但输出仍然不是所需的。
编辑3：
Another input
7
SHELDON
HSTYUPQ
EHGXBAJ
LMNNQQI
DTYUIOP
OZXCVBN
NQWERTY
7
SHELDON
Expected output:
5
My output - 1
编辑 4(已解决！(：所以问题在于将网格矩阵的列数写为 500，将其更改为 5 即可完成工作！感谢@gsamaras
法典
#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("%dn", 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] = ' ';
}
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("%dn", count);
return 0;
}
更改以下内容：
void check(char grid[][500], ......
对此：
void check(char grid[][5], ....... // that should be equal to N + 1 (5 in your case)
因为您的网格大小为 N x N + 1。以500作为维度，你扭曲了网格，当试图递归搜索它时，你不会遍历你期望遍历的网格。
如您所见，这并不灵活，因为N可能会有所不同。不能将grid声明为全局，因为它的维度不是固定的。应改用动态内存分配。
更改此设置：
scanf("%s", &word);
对此：
scanf("%s", word);
因为word是一个字符数组。
动态内存分配的完整示例：
#include <stdio.h>
#include <stdlib.h>
int vis[500][500], count;
char **get(int N, int M) { /* Allocate the array */
int i;
char **p;
p = malloc(N*sizeof(char *));
for(i = 0 ; i < N ; i++)
p[i] = malloc( M*sizeof(char) );
return p;
}
void free2Darray(char** p, int N) {
int i;
for(i = 0 ; i < N ; i++)
free(p[i]);
free(p);
}
int adj(int a, int b, int c, int d) {
// Same as in your question
}
void check(char** grid, int i, int j, int id, char word[], int n, int m) {
if(id == m) {
count++;
printf("count = %dn", count); // just to debug
}
else {
for(int p = 0; p < n; p++) {
for(int q = 0;q < 499; q++) {
//printf("p = %d, q = %d, id = %d, grid[p][q] = %c, word[id] = %cn", p, q, id, grid[p][q], word[id]);
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 = get(n, n + 1);
for(int i = 0; i < n; i++) {
scanf("%s", grid[i]);
grid[i][n] = ' ';
}
scanf("%d", &m);
char word[m+1];
scanf("%s", word);
for(int i = 0; i < n; i++) {
for(int j = 0;j < n; j++) {
//printf("i = %d, j = %d, id = %dn", i, j, id);
if(grid[i][j] == word[id]) {
vis[i][j] = 1;
check(grid, i, j, id + 1, word, n, m);
vis[i][j] = 0;
}
}
}
printf("%dn", count);
free2Darray(grid, n);
return 0;
}
输出(对于您的第一个输入(：
count = 1
count = 2
count = 3
count = 4
count = 5
count = 6
count = 7
count = 8
count = 9
count = 10
10
PS：不是问题，只是关于可读性的建议：count初始化为 0，因为它是一个全局变量，但最好在重要的时候显式初始化变量。