P1101题解

### [P1101题目链接](https://www.luogu.org/problem/P1101) ### [想获得更好的观看体验，请在博客内查看](https://www.luogu.org/blog/Frozen-lobster/p1101) ## 先说一下我的思路吧： 1. 找出首字母Y 1. 找出字母Y旁边的I，记录其扩展方向 1. 依次检查沿Y向I方向的字母 1. 若至字母G时无误记录下其单词扩展路径 1. 输出合法的单词** ### 预定义： ```cpp char s[105][105]; const string key="yizhong"; int n,idx[105][105]{}; //c++11用法，把idx数组全部初始化为0 //idx[i][j]=1 代表可成为单词，s表示原方阵，key为单词 ``` ### 主函数 ```cpp int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%s",&s[i]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(s[i][j]=='y'){ //找到单词的起点 for(int dr=-1;dr<=1;dr++) for(int dc=-1;dc<=1;dc++){ //二重循环可用常量数组替代 if(s[i+dr][j+dc]=='i') dfs(dr,dc,i,j,0); //dr，dc，代表竖直和水平共8个方向 ，找到搜索方向后进行搜索, } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ if(idx[i][j]) printf("%c",s[i][j]); else printf("*"); } //输出答案，记得换行 printf("\n"); } return 0; } ``` ### 搜索函数 ```cpp void dfs (int dr,int dc,int r,int c,int cnt){ if(cnt==7) { for(int i=1;i<=7;i++) idx[r-dr*i][c-dc*i]=1; } //搜索终点，如果可成为一个单词，令其路径上的所有字母 idx=1 if( r>=0&&r<n&&c>=0&&c<n &&s[r][c]==key[cnt]) { dfs(dr,dc,r+dr,c+dc,cnt+1); } //进行下一个字母的检查和搜索 return; } ``` ### 完整~~压行~~代码 ```cpp #include<cstdio> #include<string> using namespace std; char s[105][105]; const string key="yizhong"; int n,idx[105][105]{}; void dfs (int dr,int dc,int r,int c,int cnt){ if(cnt==7) for(int i=1;i<=7;i++) idx[r-dr*i][c-dc*i]=1; if( r>=0&&r<n&&c>=0&&c<n &&s[r][c]==key[cnt]) dfs(dr,dc,r+dr,c+dc,cnt+1); } int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%s",&s[i]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(s[i][j]=='y') for(int dr=-1;dr<=1;dr++) for(int dc=-1;dc<=1;dc++) if(s[i+dr][j+dc]=='i') dfs(dr,dc,i,j,0); for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(idx[i][j]) printf("%c",s[i][j]); else printf("*"); } printf("\n"); return 0; } ``` 点个赞再走吧qwq