洛谷 P1101 单词方阵-白红宇

洛谷 P1101 单词方阵

阅读量：6825 次

发布时间：2019-06-26

本文共 3100 字，大约阅读时间需要 10 分钟。

题目描述

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

输入：    8                     输出：    qyizhong              *yizhong    gydthkjy              gy******    nwidghji              n*i*****    orbzsfgz              o**z****    hhgrhwth              h***h***    zzzzzozo              z****o**    iwdfrgng              i*****n*    yyyygggg              y******g

输入输出格式

输入格式：

第一行输入一个数 $\le n \le 1007≤n≤100)。$

第二行开始输入 $\times nn×n的字母矩阵。$

输出格式：

突出显示单词的 $\times nn×n矩阵。$

输入样例#1：

7aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出样例#1：

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

输入样例#2：

8qyizhonggydthkjynwidghjiorbzsfgzhhgrhwthzzzzzozoiwdfrgngyyyygggg 输出样例#2：

*yizhonggy******n*i*****o**z****h***h***z****o**i*****n*y******g

解析

dfs，思路比较简单，dfs时记录一下八个方向，记录到哪一个字母了，再记录当前坐标。搜索之前先找到单词的方向，注意越界判断，之后暴力搜索即可。 代码

#include
       
        #include
        
         #include
         
          using namespace std;char mp[105][105];int book[105][105];int n;char word[8]={
     '0','y','i','z','h','o','n','g'};bool flag;int changex[9]={
     0,-1,0,1,1,1,0,-1,-1};int changey[9]={
     0,1,1,1,0,-1,-1,-1,0};//八个方向 vector
          
            vx,vy;void dfs(int xx,int yy,int num,int direct)//坐标，第几个字母，方向 {    if(num>7)    {        int m=vx.size();        for(int i=m-1;i>=0;i--)        {            int a=vx[i];            int b=vy[i];            vx.pop_back();            vy.pop_back();            book[a][b]=1;        }        flag=true;        return;    }    int newx=xx+changex[direct];    int newy=yy+changey[direct];    if(newx>n&&newx<1) return;    if(newy>n&&newy<1) return;    if(mp[newx][newy]==word[num])    {        vx.push_back(newx);        vy.push_back(newy);        num++;        dfs(newx,newy,num,direct);        if(vx.size()!=0)        {            vx.pop_back();            vy.pop_back();        }//pop_back不要过度     }    return;}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            cin>>mp[i][j];        }    }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            if(mp[i][j]=='y')            {                for(int k=1;k<=8;k++)//确定方向                 {                    int newx=i+changex[k];                    int newy=j+changey[k];                    if(newx>n&&newx<1) continue;                    if(newy>n&&newy<1) continue;//越界判断                     if(mp[newx][newy]=='i')                    {                         dfs(newx,newy,3,k);                        if(flag==true)                        {                            book[newx][newy]=1;                            book[newx-changex[k]][newy-changey[k]]=1;                             flag=false;                         }                    }                }            }        }    }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            if(book[i][j]!=1)            {                mp[i][j]='*';            }            cout<

转载于:https://www.cnblogs.com/KyleDeng/p/9758953.html

你可能感兴趣的文章