【深搜】单词方阵

叁歲伎倆 2021-12-24 08:31 225阅读 0赞

# 声明 #

--------------------

我的码风可能有点和别人不太一样（其实就是有点奇怪），大家重在意会即可。  
[原题传送门][Link 1]

# 前言 #

--------------------

作为一道被卡了1个小时才做出这道水题萌新，表示自己码风有点菜，于是决定多做一点解释，毕竟80行的代码可能确实有点水QAQ。

## \#60分骗分代码详解 ##

首先，为了便于比对单词，我建立了一个string类对象存储题目要求的单词（我表示并不清楚这个单词是否有实际意义，如果有哪位大佬知道，欢迎在评论里告诉我）  
string ans=" yizhong";

然后，n与m表示数组下标，用no表示该下标所应该对应的字母的编号，如：

int dfs(int n,int m,int no)

如果越界：  
`if(n<1||m<1||n>num||m>num) return 0;`cpp  
上深搜伪代码：

1 int dfs(int n,int m,int no) 2 { 3 if(n<1||m<1||n>num||m>num)//如果越界则返回 4 return 0; 5 if(a[n][m]==ans[no])//如果是对应字母，则继续深搜 6 { 7 if(no==7)//如果搜到最后一个，则返回1，表示深搜成功 8 { 9 book[n][m]=1; 10 return 1; 11 } 12 else 13 { 14 //搜索每一种可能 15 if(dfs(n+1,m,no+1)||dfs(n,m-1,no+1)||dfs(n,m+1,no+1)||dfs(n-1,m,no+1)||dfs(n+1,m-1,no+1)||dfs(n+1,m+1,no+1)||dfs(n-1,m-1,no+1)||dfs(n-1,m+1,no+1)) 16 { 17 //若搜索成功，标记该字符是单词的一部分 18 book[n][m]=1; 19 return 1; 20 } 21 else 22 return 0; 23 } 24 } 25 else//否则返回0 26 return 0; 27 }

大家仔细观察便会发现该代码的漏洞：他搜索所有的方向，因此如果有弯曲的字符连在一起与要求单词相同，它便认为该字符是单词的一部分，然而，题目要求必须是横或竖或斜直着相连的字符串才参与比对，故若有该类型的数据，此代码就会出错（这便是他只能作为骗分代码的原因）

最后，上你们最爱的完整代码（第一个和第三个点会WA，原因上面已经解释过，因此只能得60分）

1 #include<iostream> 2 #include <string> 3 using namespace std; 4 5 char a[102][102]; 6 bool book[102][102]={0};//标记对应字符是否是要求单词的一部分 7 int num; 8 9 int dfs(int n,int m,int no) 10 { 11 if(n<1||m<1||n>num||m>num)//如果越界则返回 12 return 0; 13 if(a[n][m]==ans[no])//如果是对应字母，则继续深搜 14 { 15 if(no==7)//如果搜到最后一个，则返回1，表示深搜成功 16 { 17 book[n][m]=1; 18 return 1; 19 } 20 else 21 { 22 //搜索每一种可能 23 if(dfs(n+1,m,no+1)||dfs(n,m-1,no+1)||dfs(n,m+1,no+1)||dfs(n-1,m,no+1)||dfs(n+1,m-1,no+1)||dfs(n+1,m+1,no+1)||dfs(n-1,m-1,no+1)||dfs(n-1,m+1,no+1)) 24 { 25 //若搜索成功，标记该字符是单词的一部分 26 book[n][m]=1; 27 return 1; 28 } 29 else 30 return 0; 31 } 32 } 33 else//否则返回0 34 return 0; 35 } 36 int main() 37 { 38 //读入 39 cin>>num; 40 for(int i=1;i<=num;i++) 41 for(int j=1;j<=num;j++) 42 { 43 cin>>a[i][j]; 44 } 45 //深搜 46 for(int i=1;i<=num;i++) 47 for(int j=1;j<=num;j++) 48 dfs(i,j,1); 49 //输出 50 for(int i=1;i<=num;i++) 51 { 52 for(int j=1;j<=num;j++) 53 { 54 if(book[i][j]) 55 cout<<a[i][j]; 56 else 57 cout<<"*"; 58 } 59 cout<<endl; 60 } 61 return 0; 62 }

# 100分AC代码详解 #

--------------------

我们说，上面的代码只能得60分的原因在于他不判断方向，而深搜所有的方向，因此会出错，解决代码也十分简单：在dfs（）函数中加一个表示方向的参数f即可：

1 int dfs(int n,int m,int no,int f) 2 { 3 if(n<1||m<1||n>num||m>num)//如果越界则返回 4 return 0; 5 if(a[n][m]==ans[no])//如果是对应字母，则继续深搜 6 { 7 if(no==7)//如果搜到最后一个，则返回1，表示深搜成功 8 { 9 book[n][m]=1; 10 return 1; 11 } 12 else 13 { 14 //有选择性的搜索 15 switch (f) 16 { 17 case 1: if(dfs(n-1,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 18 case 2: if(dfs(n-1,m,no+1,f)){book[n][m]=1;return 1;}else return 0; 19 case 3: if(dfs(n-1,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 20 case 4: if(dfs(n,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 21 /*case 5表示no==1， 22 作为第一个字母，因此是个特例，要向所有方向搜索 23 其余情况都只向一个特定方向搜索*/ 24 case 5: 25 if(dfs(n-1,m-1,no+1,1)) 26 book[n][m]=1; 27 if(dfs(n-1,m,no+1,2)) 28 book[n][m]=1; 29 if(dfs(n-1,m+1,no+1,3)) 30 book[n][m]=1; 31 if(dfs(n,m-1,no+1,4)) 32 book[n][m]=1; 33 if(dfs(n,m+1,no+1,6)) 34 book[n][m]=1; 35 if(dfs(n+1,m-1,no+1,7)) 36 book[n][m]=1; 37 if(dfs(n+1,m,no+1,8)) 38 book[n][m]=1; 39 if(dfs(n+1,m+1,no+1,9)) 40 book[n][m]=1; 41 break; 42 case 6: if(dfs(n,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 43 case 7: if(dfs(n+1,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 44 case 8: if(dfs(n+1,m,no+1,f)){book[n][m]=1;return 1;}else return 0; 45 case 9: if(dfs(n+1,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 46 } 47 48 } 49 } 50 else//如果搜到最后一个，则返回1，表示深搜成功 51 return 0; 52 }

你们最爱的100分AC完整代码：

1 #include<iostream> 2 #include <string> 3 using namespace std; 4 5 string ans=" yizhong"; 6 char a[102][102]; 7 bool book[102][102]={0}; 8 int num; 9 int dfs(int n,int m,int no,int f); 10 11 int main() 12 { 13 freopen("cs.in","r",stdin); 14 cin>>num; 15 for(int i=1;i<=num;i++) 16 for(int j=1;j<=num;j++) 17 cin>>a[i][j]; 18 for(int i=1;i<=num;i++) 19 for(int j=1;j<=num;j++) 20 dfs(i,j,1,5); 21 for(int i=1;i<=num;i++) 22 { 23 for(int j=1;j<=num;j++) 24 { 25 if(book[i][j]) 26 cout<<a[i][j]; 27 else 28 cout<<"*"; 29 } 30 cout<<endl; 31 } 32 return 0; 33 } 34 35 int dfs(int n,int m,int no,int f) 36 { 37 if(n<1||m<1||n>num||m>num)//如果越界则返回 38 return 0; 39 if(a[n][m]==ans[no])//如果是对应字母，则继续深搜 40 { 41 if(no==7)//如果搜到最后一个，则返回1，表示深搜成功 42 { 43 book[n][m]=1; 44 return 1; 45 } 46 else 47 { 48 //有选择性的搜索 49 switch (f) 50 { 51 case 1: if(dfs(n-1,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 52 case 2: if(dfs(n-1,m,no+1,f)){book[n][m]=1;return 1;}else return 0; 53 case 3: if(dfs(n-1,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 54 case 4: if(dfs(n,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 55 /*case 5表示no==1， 56 作为第一个字母，因此是个特例，要向所有方向搜索 57 其余情况都只向一个特定方向搜索*/ 58 case 5: 59 if(dfs(n-1,m-1,no+1,1)) 60 book[n][m]=1; 61 if(dfs(n-1,m,no+1,2)) 62 book[n][m]=1; 63 if(dfs(n-1,m+1,no+1,3)) 64 book[n][m]=1; 65 if(dfs(n,m-1,no+1,4)) 66 book[n][m]=1; 67 if(dfs(n,m+1,no+1,6)) 68 book[n][m]=1; 69 if(dfs(n+1,m-1,no+1,7)) 70 book[n][m]=1; 71 if(dfs(n+1,m,no+1,8)) 72 book[n][m]=1; 73 if(dfs(n+1,m+1,no+1,9)) 74 book[n][m]=1; 75 break; 76 case 6: if(dfs(n,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 77 case 7: if(dfs(n+1,m-1,no+1,f)){book[n][m]=1;return 1;}else return 0; 78 case 8: if(dfs(n+1,m,no+1,f)){book[n][m]=1;return 1;}else return 0; 79 case 9: if(dfs(n+1,m+1,no+1,f)){book[n][m]=1;return 1;}else return 0; 80 } 81 82 } 83 } 84 else//如果搜到最后一个，则返回1，表示深搜成功 85 return 0; 86 }

# 后记 #

--------------------

相信大家看到这里，便会感到深搜原来就是这么简单！记住：代码长！=晦涩难懂！无需十分在意自己的码风，能AC的代码就是好代码！最后，我辛苦敲了这么多，各位大佬能否给个赞呢？~~~

转载于:https://www.cnblogs.com/gongdakai/p/11066381.html

[Link 1]: https://www.luogu.org/problemnew/show/P1101