首页 > 其他 > 详细

深搜模板题单词方阵题解

时间:2019-08-23 21:20:55      阅读:62      评论:0      收藏:0      [点我收藏+]

题目描述 

这一题的主要思路是先找到一个“y”字符,再往8个方向搜索下一个字符,若周围有下一个字符“i”,就再向下一个方向搜索(方向不能变),然后直至搜索完“yizhong”或找不到为止;

然后用一个bool数组存储“yizhong”的坐标,最后根据bool数组的标记输出

上代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}p[101][101];
char a[101][101];    
bool b[101][101];
char f[8]={ ,y,i,z,h,o,n,g};
int d[8]={1,1,0,-1,-1,-1,0,1};
int c[8]={0,-1,-1,-1,0,1,1,1};
int n;
void dfs(int l,int r,int h,int v)
{
    if(h==1)
    for(int i=0;i<=7;i++)
    if(a[l+d[i]][r+c[i]]==f[h+1])
    {p[l+d[i]][r+c[i]].x=l;
    p[l+d[i]][r+c[i]].y=r;
    dfs(l+d[i],r+c[i],h+1,i);
    }
    if(h!=1&&h!=7)
    if(a[l+d[v]][r+c[v]]==f[h+1])
    {p[l+d[v]][r+c[v]].x=l;
    p[l+d[v]][r+c[v]].y=r;
    dfs(l+d[v],r+c[v],h+1,v);
    }
    if(h==7)
    {int i=p[l][r].x,j=p[l][r].y;
    b[l][r]=1;
        while(i!=0&&j!=0)
        {
            b[i][j]=1;
            int q=i;
            i=p[i][j].x;
            j=p[q][j].y;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {for(int j=1;j<=n;j++)
    cin>>a[i][j];
    getchar();}
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]==y)
            dfs(i,j,1,9);
    for(int i=1;i<=n;i++)
        {
        for(int j=1;j<=n;j++)
        if(b[i][j]==0)
        cout<<"*";
        else
        cout<<a[i][j];
        cout<<endl;}
        return 0;
}

 

 

深搜模板题单词方阵题解

原文:https://www.cnblogs.com/ln1225/p/11402571.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!