华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2270|回复: 8
打印 上一主题 下一主题

P1101 单词方阵

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-18 15:01:26 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

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:
*******
*******
*******
*******
*******
*******
*******

回复

使用道具 举报

13

主题

41

帖子

211

积分

中级会员

Rank: 3Rank: 3

积分
211
沙发
发表于 2018-5-20 16:52:14 | 只看该作者
#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;
}
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
 楼主| 发表于 2018-5-20 20:25:47 来自手机 | 只看该作者
很好!!!但是 105 请定义为常数  方向数组请写+1 -1 +0 以对齐
回复 支持 反对

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
地板
发表于 2018-5-26 19:03:25 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

7

主题

27

帖子

91

积分

注册会员

Rank: 2

积分
91
5#
发表于 2018-6-5 13:49:35 | 只看该作者
  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. void su(int p,int q,int x,int y)
  14. {
  15.     for(int i=0;i<=6;i++)
  16.     {
  17.         b[p+i*x][q+i*y]=true;
  18.     }
  19.     return;
  20. }

  21. void xiuxi(int p,int q,int step,int x,int y)
  22. {
  23.    
  24.     if(step==7)
  25.     {
  26.         su(p,q,x,y);
  27.         return;
  28.     }
  29.     if(p+x*step>=n || p+x*step<0 || q+y*step>=n || q+y*step<0) return;
  30.     if(a[p+x*step][q+y*step]==kk[step+1])
  31.     {
  32.         xiuxi(p,q,step+1,x,y);
  33.     }
  34.     else return;

  35.     return;
  36. }

  37. void sou1(int p,int q)
  38. {
  39.     for(int i=0;i<=7;i++)
  40.     {
  41.         int x=fuzhu[i][0];
  42.         int y=fuzhu[i][1];
  43.         if(p+x<n && q+y>=0 && p+x>=0 && q+y<n)
  44.         {
  45.             if(a[p+x][q+y]=='i')
  46.             {
  47.                 xiuxi(p,q,1,x,y);
  48.             }
  49.         }
  50.     }

  51.     return;
  52. }


  53. void nowgo()
  54. {
  55.     for(int i=0;i<n;i++)
  56.     {
  57.         for(int j=0;j<n;j++)
  58.         {
  59.             if(a[i][j]=='y')
  60.             {
  61.                 sou1(i,j);
  62.             }
  63.         }
  64.     }

  65.     return;
  66. }



  67. int main()
  68. {
  69.     scanf("%d",&n);
  70.     for(int i=0;i<n;i++)
  71.     {
  72.         cin>>a[i];
  73.     }

  74.     nowgo();

  75.     for(int i=0;i<n;i++)
  76.     {
  77.         for(int j=0;j<n;j++)
  78.         {
  79.             ///printf("%d",b[i][j]);
  80.             if(b[i][j]) printf("%c",a[i][j]);
  81.             else printf("*");
  82.         }
  83.         printf("\n");
  84.     }
  85.     return 0;
  86. }

复制代码
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
6#
 楼主| 发表于 2018-6-5 15:28:26 | 只看该作者
楼上罗同学,我为什么要你们把自己的程序写出来呢?你看我来评点你的程序:
有很多不必要的{}  到处是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}
复制代码

回复 支持 反对

使用道具 举报

9

主题

89

帖子

292

积分

华一学生

积分
292
7#
发表于 2018-6-11 22:55:36 | 只看该作者
搜索“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. }
复制代码

回复 支持 反对

使用道具 举报

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
8#
发表于 2018-9-15 23:24:12 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

0

主题

11

帖子

38

积分

新手上路

Rank: 1

积分
38
9#
发表于 2018-11-4 18:55:39 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 13:56 , Processed in 0.109882 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表