P1101 单词方阵

题目描述

给一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： 

7aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出样例#1： 

************************************************* 思路：搜索。

#include
           
            #include
            
             #include
             
              #include
              
               using namespace std;int n,flag;int dx[8]={
         0,0,1,1,1,-1,-1,-1};int dy[8]={
         1,-1,1,-1,0,1,-1,0};char ans[8]={
         'y','i','z','h','o','n','g'};char s[101],map[101][101],vis[101][101];void dfs(int x,int y,int k,int tot){    if(tot==7)    return ;    int cx=x+dx[k];    int cy=y+dy[k];    if(cx>=1&&cx<=n&&cy>=1&&cy<=n&&ans[tot]==map[cx][cy])        dfs(cx,cy,k,tot+1);    else flag=1;}void dfs1(int x,int y,int k,int tot){    vis[x][y]=1;    if(tot==7)    return ;    int cx=x+dx[k];    int cy=y+dy[k];    if(cx>=1&&cx<=n&&cy>=1&&cy<=n&&ans[tot]==map[cx][cy])        dfs1(cx,cy,k,tot+1);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){         scanf("%s",s);        for(int j=0;j