洛谷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：

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

输出样例#1：

*******
*******
*******
*******
*******
*******
*******

记录一下搜的方向，递归标记就行

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 const int mxn=120;
 9 int mx[9]={0,1,0,-1,0,1,1,-1,-1},
10     my[9]={0,0,1,0,-1,1,-1,1,-1};
11 char s[mxn]="yizhong";
12 char mp[mxn][mxn];
13 int n;
14 inline bool check(int x,int y){
15     if(x<0 || x>=n || y<0 || y>=n)return 0;
16     return 1;
17 }
18 int vis[mxn][mxn];
19 bool dfs(int x,int y,int last,int dir){
20     int i,j;
21     if(last==6)return 1;
22     int nx=x+mx[dir],ny=y+my[dir];
23     if(!check(nx,ny))return 0;
24     if(mp[nx][ny]==s[last+1]){
25         if(dfs(nx,ny,last+1,dir)){
26             vis[nx][ny]=1;
27             return 1;
28         }
29     }
30     return 0;
31 }
32 int main(){
33     scanf("%d",&n);
34     int i,j;
35     for(i=0;i<n;i++){
36         scanf("%s",mp[i]);
37     }
38     for(i=0;i<n;i++)
39      for(j=0;j<n;j++){
40          if(mp[i][j]=='y'){
41              for(int k=1;k<=8;k++)
42               if(dfs(i,j,0,k))vis[i][j]=1;
43          }
44      }
45     for(i=0;i<n;i++)
46      for(j=0;j<n;j++){
47          if(vis[i][j])printf("%c",mp[i][j]);
48          else printf("*");
49          if(j==n-1)printf("
");
50      }
51     return 0;
52 }