Luogu 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 //2018年4月2日23:09:45
 2 #include <iostream>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 101;
 7 
 8 int n;
 9 char a[N][N];
10 bool mark[N][N];
11 int d[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{0,1},{-1,0},{0,-1}};
12 char cmp[7] = {'y', 'i', 'z', 'h', 'o', 'n', 'g'};
13 
14 
15 void check(int x, int y){
16     int i;
17     for(int k=0; k<8; k++){
18         for(i=1; i<=6; i++){
19             int xx = x+i*d[k][0], yy = y+i*d[k][1];
20             if(xx<1 || xx>n || yy<1 || yy>n) break;
21             if(a[xx][yy] != cmp[i]) break;
22         }
23         if(i == 7)
24             for(int j=0; j<=6; j++)
25                 mark[x+d[k][0]*j][y+d[k][1]*j] = 1;
26     }
27 }
28 
29 int main(){
30     scanf("%d", &n);
31     for(int i=1; i<=n; i++)
32         scanf("%s", a[i]+1);
33         
34     for(int i=1; i<=n; i++)
35         for(int j=1; j<=n; j++)
36             if(a[i][j] == 'y')
37                 check(i, j);
38     for(int i=1; i<=n; i++){
39         for(int j=1; j<=n; j++)
40             if(mark[i][j]) printf("%c", a[i][j]);
41             else printf("*");
42         printf("
"); 
43     }
44     
45     
46     return 0;
47 }