华师一附中OI组

标题: P1101 单词方阵 [打印本页]

---

作者: admin    时间: 2018-5-18 15:01
标题: P1101 单词方阵

https://www.luogu.org/problemnew/show/P1101

题目描述
给一nXn的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用“*”代替，以突出显示单词。例如：

输入：
    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：
*******
*******
*******
*******
*******
*******
*******

---

作者: YTC    时间: 2018-5-20 16:52
#include<iostream>
using namespace std;
string st="yizhong";
int p;
char a[105][105];
bool b[105][105];
char c[105][105];
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};
void mysearch(int i,int j,int n,int k)
{
    //if(i<=0||i>n||j<=0||j>n) return;
    if(n>=7)
    {
        for(int ii=1;ii<=p;ii++)
            for(int jj=1;jj<=p;jj++)
            if(b[ii][jj]) c[ii][jj]=a[ii][jj];
    }
    else
    if(n==0)
        if(a[i][j]==st[n])
    {
        b[i][j]=true;
        for(int k=1;k<=8;k++)
            mysearch(i+dx[k],j+dy[k],n+1,k);
        b[i][j]=false;
    }
    if(n>0&&n<7)
    {
        if(a[i][j]==st[n])
        {
            b[i][j]=true;
            mysearch(i+dx[k],j+dy[k],n+1,k);
            b[i][j]=false;
        }
    }
}
int main()
{
    cin>>p;
    for(int i=1;i<=p;i++)
        for(int j=1;j<=p;j++)
        cin>>a[i][j];
    for(int i=1;i<=p;i++)
        for(int j=1;j<=p;j++)
        mysearch(i,j,0,0);
    for(int i=1;i<=p;i++)
    {
        for(int j=1;j<=p;j++)
    {
        if(c[i][j]) cout<<c[i][j];
        else cout<<'*';
    }
    cout<<endl;
    }
    return 0;
}

---

作者: admin    时间: 2018-5-20 20:25
很好！！！但是 105 请定义为常数  方向数组请写+1 -1 +0 以对齐

---

作者: 黄煦喆    时间: 2018-5-26 19:03

1. #include<iostream>
   
2. #include<map>
   
3. using namespace std;
   
4. int n;
   
5. char a[102][102];
   
6. char b[102][102];
   
7. int gx[9]= {0,-1,-1,-1,+0,+1,+1,+1,+0};
   
8. int gy[9]= {0,-1,+0,+1,+1,+1,+0,-1,-1};
   
9. map<char,char>m;
   
10. void check(int x,int y,int dir,int s)
    
11. {
    
12.     if(s==0)return;
    
13.     else
    
14.     {
    
15.         b[x][y]=a[x][y];
    
16.         int kx=x-gx[dir];
    
17.         int ky=y-gy[dir];
    
18.         check(kx,ky,dir,s-1);
    
19.     }
    
20. }
    
21. void ms(int x,int y,int dir,int s)
    
22. {
    
23.     if(s==7&&a[x][y]=='g')check(x,y,dir,s);
    
24.     int tx=x+gx[dir];
    
25.     int ty=y+gy[dir];
    
26.     if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==m[a[x][y]])
    
27.     {
    
28.         ms(tx,ty,dir,s+1);
    
29.     }
    
30. }
    
31. int main()
    
32. {
    
33.     cin>>n;
    
34.     m.insert(make_pair('y','i'));
    
35.     m.insert(make_pair('i','z'));
    
36.     m.insert(make_pair('z','h'));
    
37.     m.insert(make_pair('h','o'));
    
38.     m.insert(make_pair('o','n'));
    
39.     m.insert(make_pair('n','g'));
    
40.     for(int i=1; i<=n; i++)
    
41.         for(int j=1; j<=n; j++)cin>>a[i][j];
    
42.     for(int i=1; i<=n; i++)
    
43.         for(int j=1; j<=n; j++)
    
44.             if(a[i][j]=='y')
    
45.                 for(int k=1; k<=8; k++)ms(i,j,k,1);
    
46.     for(int i=1; i<=n; i++)
    
47.     {
    
48.         for(int j=1; j<=n; j++)
    
49.             if(b[i][j]>='a'&&b[i][j]<='z')cout<<b[i][j];
    
50.             else cout<<'*';
    
51.         cout<<endl;
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码

---

作者: 胡雨菲菲    时间: 2018-6-5 13:49

1. #include <cstdio>
   
2. #include <iostream>
   
3. using namespace std;
   
4. ///yizhong 7
   
5. int n;
   
6. bool b[103][103];
   
7. char a[103][103];
   
8. char kk[8]={'.','y','i','z','h','o','n','g'};
   
9. int fuzhu[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{0,-1},{-1,-1},{-1,0}};
   
10. ///y
    
11. ///i
    
12. ///记录方向k
    
13. 
    
14. void su(int p,int q,int x,int y)
    
15. {
    
16.     for(int i=0;i<=6;i++)
    
17.     {
    
18.         b[p+i*x][q+i*y]=true;
    
19.     }
    
20.     return;
    
21. }
    
22. 
    
23. void xiuxi(int p,int q,int step,int x,int y)
    
24. {
    
25.    
    
26.     if(step==7)
    
27.     {
    
28.         su(p,q,x,y);
    
29.         return;
    
30.     }
    
31.     if(p+x*step>=n || p+x*step<0 || q+y*step>=n || q+y*step<0) return;
    
32.     if(a[p+x*step][q+y*step]==kk[step+1])
    
33.     {
    
34.         xiuxi(p,q,step+1,x,y);
    
35.     }
    
36.     else return;
    
37. 
    
38.     return;
    
39. }
    
40. 
    
41. void sou1(int p,int q)
    
42. {
    
43.     for(int i=0;i<=7;i++)
    
44.     {
    
45.         int x=fuzhu[i][0];
    
46.         int y=fuzhu[i][1];
    
47.         if(p+x<n && q+y>=0 && p+x>=0 && q+y<n)
    
48.         {
    
49.             if(a[p+x][q+y]=='i')
    
50.             {
    
51.                 xiuxi(p,q,1,x,y);
    
52.             }
    
53.         }
    
54.     }
    
55. 
    
56.     return;
    
57. }
    
58. 
    
59. 
    
60. void nowgo()
    
61. {
    
62.     for(int i=0;i<n;i++)
    
63.     {
    
64.         for(int j=0;j<n;j++)
    
65.         {
    
66.             if(a[i][j]=='y')
    
67.             {
    
68.                 sou1(i,j);
    
69.             }
    
70.         }
    
71.     }
    
72. 
    
73.     return;
    
74. }
    
75. 
    
76. 
    
77. 
    
78. int main()
    
79. {
    
80.     scanf("%d",&n);
    
81.     for(int i=0;i<n;i++)
    
82.     {
    
83.         cin>>a[i];
    
84.     }
    
85. 
    
86.     nowgo();
    
87. 
    
88.     for(int i=0;i<n;i++)
    
89.     {
    
90.         for(int j=0;j<n;j++)
    
91.         {
    
92.             ///printf("%d",b[i][j]);
    
93.             if(b[i][j]) printf("%c",a[i][j]);
    
94.             else printf("*");
    
95.         }
    
96.         printf("\n");
    
97.     }
    
98.     return 0;
    
99. }
    
100. 
     

复制代码

---

作者: admin    时间: 2018-6-5 15:28
楼上罗同学，我为什么要你们把自己的程序写出来呢？你看我来评点你的程序：
有很多不必要的{}  到处是return 不结构化！
你的这一段：

1. bool b[103][103];
   
2. char a[103][103];
   
3. char kk[8]={'.','y','i','z','h','o','n','g'};
   
4. int fuzhu[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{0,-1},{-1,-1},{-1,0}};

复制代码

写成我这样的你觉得如何？

1. const int mm=103;
   
2. bool b[m][m];
   
3. char a[m][m];
   
4. string kk=".yizhong";
   
5. int fuzhu[8][2]={-1,-1,-1,+0,+0,+1,+1,+1,
   
6.                          -1,+0,+1,-1,+1,-1,+0,+1}

复制代码

---

作者: 张笑宇    时间: 2018-6-11 22:55
搜索“y”

1. #include<iostream>
   
2. using namespace std;
   
3. char m[9]=" yizhong";
   
4. char a[110][110];
   
5. bool b[110][110];
   
6. int n,i,j,x[10010],y[10010],t;
   
7. int dx[10]= {0,-1,+0,+1,+1,+1,+0,-1,-1};
   
8. int dy[10]= {0,+1,+1,+1,+0,-1,-1,-1,+0};
   
9. int main()
   
10. {
    
11.     cin>>n;
    
12.     t=0;
    
13.     for (i=1; i<=n; i++)
    
14.         for (j=1; j<=n; j++)
    
15.         {
    
16.             cin>>a[i][j];
    
17.             if (a[i][j]=='y')
    
18.             {
    
19.                 t++;
    
20.                 x[t]=i;
    
21.                 y[t]=j;
    
22.             }
    
23.         }
    
24.     for (int it=1; it<=t; it++) ///搜索‘y’
    
25.     {
    
26.         int xx=x[it],yy=y[it];///'y'坐标(x[it],y[it]);
    
27.         for (i=1; i<=8; i++) ///8个方向搜索i
    
28.         {
    
29.             bool bb=true;
    
30.             int sx=xx,sy=yy;///sx,sy计数 到第几位了
    
31.             for (j=1;j<=6;j++)
    
32.             {
    
33.                 sx=sx+dx[i];
    
34.                 sy=sy+dy[i];
    
35.                 if (sx<1||sx>n||sy<1||sy>n||a[sx][sy]!=m[j+1]) bb=false;
    
36.             }
    
37.             if (bb)
    
38.             {
    
39.                 for (j=0;j<=6;j++)
    
40.                 {
    
41.                     b[sx][sy]=true;///回溯标记
    
42.                     sx=sx-dx[i];
    
43.                     sy=sy-dy[i];
    
44.                 }
    
45.             }
    
46.         }
    
47.     }
    
48.     for (i=1;i<=n;i++)
    
49.     {
    
50.         for (j=1;j<=n;j++)
    
51.         {
    
52.             if (b[i][j]) cout<<a[i][j];
    
53.             else cout<<"*";
    
54.         }
    
55.         cout<<endl;
    
56.     }
    
57.     return 0;
    
58. }

复制代码

---

作者: universehyf    时间: 2018-9-15 23:24

1. #include<iostream>
   
2. using namespace std;
   
3. string s[110],ans[110];
   
4. #define FOR(iii,nn,m) for(int iii=nn;iii<=m;iii++)
   
5. int dr[8]={-1,-1,-1,0,0,1,1,1};
   
6. int dc[8]={-1,0,1,-1,1,-1,0,1};
   
7. int n,tr,tc;
   
8. int main()
   
9. {
   
10.     cin>>n;
    
11.     FOR(i,0,n-1)
    
12.         cin>>s[i];
    
13.     FOR(i,0,n-1) FOR(j,0,n-1)
    
14.         ans[i]+='*';
    
15.     FOR(i,0,n-1) FOR(j,0,n-1)
    
16.     if(s[i][j]=='y')
    
17.     {
    
18.         FOR(k,0,7)
    
19.         {
    
20.             tr=i;tc=j;bool bb=true;
    
21.             FOR(kk,1,6)
    
22.             {
    
23.                 tr+=dr[k];tc+=dc[k];
    
24.                 if(tr<0||tc<0||tr>=n||tc>=n) {bb=0;break;}
    
25.                 if(kk==1&&s[tr][tc]!='i') {bb=0;break;}
    
26.                 if(kk==2&&s[tr][tc]!='z') {bb=0;break;}
    
27.                 if(kk==3&&s[tr][tc]!='h') {bb=0;break;}
    
28.                 if(kk==4&&s[tr][tc]!='o') {bb=0;break;}
    
29.                 if(kk==5&&s[tr][tc]!='n') {bb=0;break;}
    
30.                 if(kk==6&&s[tr][tc]!='g') {bb=0;break;}
    
31.             }
    
32.             if(bb)
    
33.             {
    
34.                 tr=i;tc=j;
    
35.                 FOR(kk,0,6){ans[tr][tc]=s[tr][tc];tr+=dr[k];tc+=dc[k];}
    
36.             }
    
37.         }
    
38.     }
    
39.     FOR(i,0,n-1)
    
40.     {FOR(j,0,n-1)cout<<ans[i][j];cout<<endl;}
    
41.     return 0;
    
42. }

复制代码

---

作者: type尧    时间: 2018-11-4 18:55

1. //
   
2. #include<bits/stdc++.h>
   
3. #define maxn 110
   
4. using namespace std;
   
5. int n;
   
6. char ch[maxn][maxn];
   
7. string ss="yizhong";
   
8. bool book[maxn][maxn];
   
9. int move[8][2]={{-1,-1},{-1,0},{1,0},{1,1},{0,1},{0,-1},{-1,1},{1,-1}};
   
10. int sx[7];
    
11. int sy[7];
    
12. int xy[maxn*maxn];
    
13. int xx[maxn*maxn];
    
14. int k;
    
15. bool f=0;
    
16. void getdata()
    
17. {
    
18.         k=-1;
    
19.         cin>>n;
    
20.         for(int i=1;i<=n;i++)
    
21.                 for(int j=1;j<=n;j++){
    
22.                         cin>>ch[i][j];
    
23.                         if(ch[i][j]=='y'){
    
24.                                 k++;
    
25.                                 xx[k]=i;
    
26.                                 xy[k]=j;
    
27.                         }
    
28.                 }
    
29.         return;
    
30. }
    
31. void mark()
    
32. {
    
33.         for(int i=0;i<=6;i++)
    
34.                 book[sx[i]][sy[i]]=1;
    
35.         memset(sx,0,sizeof(sx));
    
36.         memset(sy,0,sizeof(sy));
    
37.                 return;
    
38. }
    
39. void dfs(int x,int y,int t,int s)
    
40. {
    
41.     if(x<0|x>n+1||y<0||y>n+1) {
    
42.         memset(sx,0,sizeof(sx));
    
43.         memset(sy,0,sizeof(sy));
    
44.         return;
    
45.     }
    
46.         if(t==7){
    
47.                 mark();
    
48.                 return;
    
49.         }
    
50.         if(ch[x][y]!=ss[t]) {
    
51.         memset(sx,0,sizeof(sx));
    
52.         memset(sy,0,sizeof(sy));
    
53.         return;
    
54.     }
    
55.         sx[t]=x;
    
56.         sy[t]=y;
    
57.         dfs(x+move[s][0],y+move[s][1],t+1,s);
    
58.         return;
    
59. }
    
60. void print()
    
61. {
    
62.         for(int i=1;i<=n;i++){
    
63.                 for(int j=1;j<=n;j++)
    
64.                         if(book[i][j])
    
65.                                 cout<<ch[i][j];
    
66.                         else cout<<"*";
    
67.                 cout<<endl;
    
68.         }
    
69.         return;
    
70. }
    
71. int main()
    
72. {
    
73.         getdata();
    
74.         for(int i=0;i<=k;i++){
    
75.                 for(int j=0;j<8;j++)
    
76.                         dfs(xx[i],xy[i],0,j);
    
77.         }
    
78.         print();
    
79.         return 0;
    
80. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2