题目描述
给一nXn的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间[color=red]可以[/color]交叉,因此有可能共用字母。输出时，将不是单词的字母用“*”代替，以突出显示单词。例如：
输入：8输出：
qyizhong *yizhong gydthkjy gy****** nwidghji n*i***** orbzsfgz o**z**** hhgrhwth h***h*** zzzzzozo z****o** iwdfrgng i*****n* yyyygggg y******g输入输出格式
输入格式：
第一行输入一个数n。(7<=n<=100)。
第二行开始输入nXn的字母矩阵。
输出格式：
突出显示单词的nXn矩阵。
输入输出样例
输入样例#1： 复制
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
输出样例#1： 复制
*******
*******
*******
*******
*******
*******
*******
算法分析：
回溯搜索，我们可以在原数组找到y，然后回溯做，将yizhong进入一个数组a，然后回溯比较，这题应该降低了不少难度，因为它的路径是一定的，所以回溯时我们可以把方向传递过去，具体看代码。
代码实现：
#include<bits/stdc++.h>
using namespace std;
int n,flag[42]={0};
char ch[105][105],ch1[105][105],be='y';
char a[8]="izhong"; //保存字母
int dx[8]={1,0,1,0, 1, -1,-1,-1},dy[8]={1,1,0,-1,-1,-1,1,0};
int dfs(int,int,int,int);
int main()
{cin>>n;cin.get(); //注意cin不吸收空格for(int i=1;i<=n;i++)cin>>ch[i]; //要是gets 洛谷不叫过，我都快吐血了memset(ch1,'*',sizeof(ch1)); //初始化ch1for(int i=1;i<=n;i++) //这里要注意字符数组的下标的特殊性for(int j=0;j<=n;j++) //一定要从0开始{if(ch[i][j]=='y') //找到y，回溯dfs(i,j,0,-1);}for(int i=1;i<=n;i++){for(int j=0;j<n;j++)cout<<ch1[i][j];cout<<endl;}return 0;
}
int dfs(int x,int y,int i,int f) //x，y表示坐标，i表示第几个字母，f表示方向
{int k;if(i==0) //如果是第一个字母{for(k=0;k<8;k++){int x1=x+dx[k];int y1=y+dy[k];if(ch[x1][y1]==a[i]&&x1>=1&&x1<=n&&y1>=0&&y1<n)dfs(x1,y1,i+1,k);}return 0;}else if(i<=5) //中间验证是否满足{int x1=x+dx[f];int y1=y+dy[f];if(ch[x1][y1]==a[i]&&x1>=1&&x1<=n&&y1>=0&&y1<n)dfs(x1,y1,i+1,f);}if (i==6) //验证完毕，回溯过去，（很好的办法）{int x1=x,y1=y;for(int j=1;j<=7;j++){ch1[x1][y1]=ch[x1][y1];//将符合的字母复制到ch1x1=x1-dx[f];y1=y1-dy[f];}}return 0;
}