洛谷 P1101单词方阵

我已经,是这个世界上,最幸福的女孩了                                                                         ——《末日时在做什么,有没有空,可以来拯救吗?》

题目:https://www.luogu.org/problem/P1101

这一题开始我居然没看懂这是什么意思,我甚至以为是每一行一个判断,然后直接把我搞懵,直到被“基”房的某位道友:Old_fox 点拨了一下,我才搞懂这道题的意思。

这题主要就是说,一个矩阵,从每一个点,向八个方向去找,看能不能出现yizhong,最后把不能的全部变成*,很简单。

唯一需要注意的就是从每个点出发后,不能中途改变方向,所以——

在搜索外面先确定方向啊!

上代码:

#include<bits/stdc++.h>
using namespace std; 
int dx[9]={0,1,-1,1,-1,1,-1,0,0};
int dy[9]={0,0,0,1,-1,-1,1,1,-1};
char a[105][105],ans[10]={"yizhong"};
bool b[105][105]={false};
int n,h[10][3];
void dfs(int z,int x,int y,int t)//没有大循环的搜索,sao吧! 
{
    int xx=x+dx[z];
    int yy=y+dy[z];
    if(a[xx][yy]==ans[t])
    {
        h[t][1]=xx;
        h[t][2]=yy;
        if(t==6)
          for(int i=0;i<=6;i++)
            b[h[i][1]][h[i][2]]=true;//置为1 
        else dfs(z,xx,yy,t+1);
        h[t][1]=0;
        h[t][2]=0;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%s",a[i]);
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
        {
          if(a[i][j]=='y')//进入搜索的前提是当前值为y 
            {
            for(int k=1;k<=8;k++)//判断方向 
              {
                    if(a[i+dx[k]][j+dy[k]]=='i')
                    {
                        h[0][1]=i;
                        h[0][2]=j;
                    dfs(k,i,j,1);//把方向,当前坐标放入搜索 
                }    
            }
          }  
        }
    }
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
      {
          if(b[i][j]==true) printf("%c",a[i][j]);
          else printf("*");
      }
      printf("\n");
    }//输出 
    return 0;
}
上一篇:常用技巧—离散化


下一篇:题解 洛谷P5027 【Barracuda】(高斯消元)