单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
代码解题如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
int pi,pj; //static int r[100][100]; void f( char ** board, int n , int m, int x, int y, char * word, int p, int **r, int *rz){ int a[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; // printf(" %d ",r[x][y]); int nx,ny; int i,j; int cc=0; int l=0; int zx,zy; //printf("%d ",r); // r[x][y]=1; //printf(" --p %d %d ",p,rz); if (m>=3)r[0][3]=0; //printf("%d %c ",r[0][3],word[p]); for (i=0;i<4;i++){ nx=a[i][0]+x; ny=a[i][1]+y; // if(nx==2)printf(" --nx ny %d %d %c",nx,ny,word[p]); if (nx>=0&&nx<=n&&ny>=0&&ny<=m){ if (r[nx][ny]>=1 &&r[nx][ny]<=p*2&&board[nx][ny]==word[p-1]){ r[nx][ny]++; // printf("%d %d ",nx,ny); f(board,n,m,nx,ny,word,p,r,rz); // f(board,n,m,pi,pj,word,p,r,rz); // f(board,n,m,0,0,word,p,r,rz); } if (r[nx][ny]==0){ // printf("ddf sa "); if (board[nx][ny]==word[p]){ for (j=0;j<4&&j!=i;j++){ zx=a[i][0]+x; zy=a[i][1]+y; if (board[zx][zy]==word[p]) { // printf("&& %c %d %d ",word[p],zx,zy); r[zx][zy]=0; // if(zx==0&&zy==3) // printf("r %d %d %d ",r[zx][zy],zx,zy); } } // printf(" nx ny %d %d %c",nx,ny,word[p]); // p++; // cc++; // printf("-- %c",word[p]); r[nx][ny]=1; printf ( "r %d %d %d %d " ,r[nx][ny],nx,ny); f(board,n,m,nx,ny,word,p+1,r,rz); } } } } // printf(" --p %d %d ",p,rz); // if(cc==0){r[x][y]=0;} if (word[p]== '\0' ) { // printf(" **p %d %d",p,rz); *rz=1;} // // return true; } bool exist( char ** board, int boardSize, int * boardColSize, char * word){ int i,j; int n=boardSize-1; int m=boardColSize[0]-1; int p=1; int x=0,y=0; int row; int z,w; int rz=0; // r[x][y]=1; // printf("-- %d ",rz); int **r = ( int **) malloc ( sizeof ( int *) *boardSize ); for (row = 0 ; row < boardSize; row++) { r[row] = ( int *) malloc ( sizeof ( int ) * boardColSize[0]); memset (r[row],0, sizeof ( int ) * boardColSize[0]); } // printf("%d %d ",n,m); for (i=0;i<=n;i++){ for (j=0;j<=m;j++){ // printf("%c ",board[i][j]); if (board[i][j]==word[0]){ for (z=0;z<=n;z++){ for (w=0;w<=m;w++){ r[z][w]=0; // printf("%c ",board[i][j]); } } r[i][j]=1; pi=i; pj=j; f(board,n,m,i,j,word,p,r,&rz); } } } // printf(" zz %d ",rz); if (rz==1) return true ; else return false ; } |
到此这篇关于c语言单词搜索的实现的文章就介绍到这了,更多相关c语言单词搜索内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!
原文链接:https://blog.csdn.net/weixin_43327597/article/details/124221414