洛谷P1101 单词方阵【DFS】

给一n \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

输入输出格式

输入格式：

第一行输入一个数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： 复制

*******

*******

*******

*******

*******

*******

*******

思路：深搜有点麻烦，其实可以暴力？

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

char s[105][105],c[7]="izhong";

int mark[105][105];

int next[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};

int n,dx,dy;

void dye(int x,int y,int step,int directon)

{

    if(step >= 7)

        return;

    mark[x][y]=1;

    dx=x+next[directon][0];

    dy=y+next[directon][1];

    dye(dx,dy,step+1,directon);

}

void dfs(int x,int y,int step,int direction)

{

    if(x<0 || y<0 || x>n || y>n)

        return;

    if(step >= 6)

    {

        dye(x,y,0,7-direction);

        return;

    }

    dx=x+next[direction][0];

    dy=y+next[direction][1];

    if(s[dx][dy] != c[step])

        return;

    else

        dfs(dx,dy,step+1,direction);

}

int main()

{

    scanf("%d",&n);

    for(int i=0;i<n;++i)

    {

        scanf("%s",s[i]);

    }

    for(int i=0;i<n;++i)

    {

        for(int j=0;j<n;++j)

        {

            if(s[i][j]=='y')

            {

                for(int k=0;k<=7;++k)

                dfs(i,j,0,k);

            }

        }

    }

    for(int i=0;i<n;++i)

    {

        for(int j=0;j<n;++j)

        {

            if(!mark[i][j])

                printf("*");

            else

                printf("%c",s[i][j]);

        }

        printf("\n");

    }

    return 0;

}

巴特西

洛谷P1101 单词方阵【DFS】

输入输出格式

输入输出样例

最新文章

热门文章