洛谷 P1101 单词方阵 题解

题源：来自洛谷深度优先搜索专题

题目

题目描述

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

输入：

8 输出：

qyizhong yizhong

gydthkjy gy*****

nwidghji ni*****

orbzsfgz oz***

hhgrhwth hh***

zzzzzozo zo**

iwdfrgng i*****n

yyyygggg y****g

输入输出格式

输入格式：

第一行输入一个数nn。(7 \le n \le 1007≤n≤100)。

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

输出格式：

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

输入输出样例

输入样例#1：

7

aaaaaaa

aaaaaaa

aaaaaaa

aaaaaaa

aaaaaaa

aaaaaaa

aaaaaaa

输出样例#1：

输入样例#2：

8

qyizhong

gydthkjy

nwidghji

orbzsfgz

hhgrhwth

zzzzzozo

iwdfrgng

yyyygggg

输出样例#2：

yizhong

gy*****

ni*****

oz***

hh***

zo**

i*****n

y****g

本人第一次AC代码：

#include <bits/stdc++.h>

using namespace std;
const int mod=1e10+7;
typedef long long int ll;
int n;
char mapp[101][101];
int size[101][101];
int dist[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,-1,-1,1,-1};
int vist[101][101];
struct vist
{
    int x;
    int y;
}c[101];
void dfs(int x,int y,int k)
{
    if(size[x][y]==7)
    {
        for(int i=1;i<=7;i++)
        {
            vist[c[i].x][c[i].y]=1;
        }
        return ;
    }
    int xx=x+dist[k][0];
    int yy=y+dist[k][1];
    if(size[xx][yy]==size[x][y]+1&&xx>=1&&xx<=n&&yy>=1&&yy<=n)
    {
        if(size[xx][yy]==7){
        c[size[xx][yy]].x=xx;
        c[size[xx][yy]].y=yy;
        }
        c[size[x][y]].x=x;
        c[size[x][y]].y=y;
        dfs(xx,yy,k);
    }
}
int main()
{
    cin >>n;
    memset(size,0,sizeof(size));
    memset(vist,0,sizeof(vist));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>mapp[i][j];
            switch (mapp[i][j])
            {
                case 'y': size[i][j]=1;break;//总感觉这里能优化，换个方式表示
                case 'i': size[i][j]=2;break;
                case 'z': size[i][j]=3;break;
                case 'h': size[i][j]=4;break;
                case 'o': size[i][j]=5;break;
                case 'n': size[i][j]=6;break;
                case 'g': size[i][j]=7;break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(size[i][j]==1)
            {
                for(int a=0;a<8;a++)
                {
                    int xx=i+dist[a][0];
                    int yy=j+dist[a][1];
                    if(size[xx][yy]==2)
                    {
                        dfs(i,j,a);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vist[i][j]==1)
                cout <<mapp[i][j];
            else cout <<"*";
        }
        cout <<endl;
    }
    return 0;
}

           

可能参数的设置和思路的分支点有问题，导致此题的代码量有些长，但运行速度15ms还是非常可观的；等到了学校再改进一下；

好吧 闲着没事干更新一下参数设置：

#include <bits/stdc++.h>

using namespace std;
const int mod=1e10+7;
typedef long long int ll;
int n,cot,a=1;
char mapp[101][101];
int dist[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,-1,-1,1,-1};
int vist[101][101];
char stander[100]={"yizhong"};
struct vist
{
    int x;
    int y;
}c[7];
void dfs(int x,int y,int k,int cot)
{
    if(cot==7)
    {
        for(int i=1;i<=7;i++)
        {
            vist[c[i].x][c[i].y]=1;
        }
        return ;
    }
    int xx=x+dist[k][0];
    int yy=y+dist[k][1];
    if(mapp[xx][yy]==stander[cot]&&xx>=1&&xx<=n&&yy>=1&&yy<=n)
    {
        if(cot==6)
        {
            c[cot+1].x=xx;
            c[cot+1].y=yy;
        }
        c[cot].x=x;
        c[cot].y=y;
        dfs(xx,yy,k,cot+1);
    }
}
int main()
{
    cin >>n;
    memset(vist,0,sizeof(vist));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>mapp[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mapp[i][j]=='y')
            {
                for(int a=0;a<8;a++)
                {
                    int xx=i+dist[a][0];
                    int yy=j+dist[a][1];
                    if(mapp[xx][yy]=='i')
                    {
                        dfs(i,j,a,1);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vist[i][j]==1)
                cout <<mapp[i][j];
            else cout <<"*";
        }
        cout <<endl;
    }
    return 0;
}

           

代码量还是有点大，我去参考一下大佬的思路吧…