P1101 单词方阵（洛谷训练场）题解

忘是亡心i 2022-12-28 07:24 158阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  输入
     *   *  输入\#1
         *  输入\#2
     *  输出
     *   *  输出\#1
         *  输出\#2
     *  算法分析
     *  解题标程

--------------------

# 题目描述 #

给一n×n的字母方阵，内可能蕴含多个“`yizhong`”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。

输出时，将不是单词的字母用`*`代替，以突出显示单词。例如：

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

## 输入格式 ##

> 第一行输入一个数n。  
> 第二行开始输入n×n的字母矩阵。

## 输出格式 ##

> 突出显示单词的n×n矩阵。

## 输入 ##

### 输入\#1 ###

7
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa

### 输入\#2 ###

8
    qyizhong
    gydthkjy
    nwidghji
    orbzsfgz
    hhgrhwth
    zzzzzozo
    iwdfrgng
    yyyygggg

## 输出 ##

### 输出\#1 ###

\*\*\*\*\*\*\*
    \*\*\*\*\*\*\*
    \*\*\*\*\*\*\*
    \*\*\*\*\*\*\*
    \*\*\*\*\*\*\*
    \*\*\*\*\*\*\*
    \*\*\*\*\*\*\*

### 输出\#2 ###

\*yizhong
    gy\*\*\*\*\*\*
    n\*i\*\*\*\*\*
    o\*\*z\*\*\*\*
    h\*\*\*h\*\*\*
    z\*\*\*\*o\*\*
    i\*\*\*\*\*n\*
    y\*\*\*\*\*\*g

## 算法分析 ##

这道题是个定向深搜。  
一开始我以为要以`y`为起点对其周围搜索`i`，然后以`i`为第二个点搜索`z`，依次类推。  
但是这道题只要确定`y`的位置以及周围`i`的方向，然后进行定点搜索就可以解决。

## 解题标程 ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    typedef struct node
    {
        
        int x,y;
    }node;
    
    node to[8]={
        {
        1,1},{
        1,-1},{
        -1,1},{
        -1,-1},{
        1,0},{
        -1,0},{
        0,-1},{
        0,1}};
    node road[7];
    char ch[8]={
        'y','i','z','h','o','n','g'};
    int n;
    int ans[1005][1005];
    int map[1005][1005];
    char s[1005][1005];
    
    void dfs(int x,int y,int k,int step)
    {
        
        road[step].x=x;
        road[step].y=y;
        if(step==6){
        
            for(int i=0;i<7;i++)
                ans[road[i].x][road[i].y]=1;
            return;
        }
        int nx=x+to[k].x;
        int ny=y+to[k].y;
            
        if(step==6||s[nx][ny]==ch[step+1]){
        
            //记录路径开始
            road[step+1].x=nx;
            road[step+1].y=ny;
            //记录路径结束
            dfs(nx, ny, k, step+1);
        }
        return;
    }
    
    int main()
    {
        
        cin >> n;
        
        memset(ans, 0, sizeof(ans));
        memset(map, 0, sizeof(map));
        for(int i=0;i<n;i++)
            cin >> s[i];
        
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
        
                if(s[i][j]=='y'){
           //找到'y'的位置
                    for(int k=0;k<8;k++)
                        if(s[i+to[k].x][j+to[k].y]=='i'){
           //找到'i'的方向进行搜索
                            map[i][j]=1;
                            dfs(i,j,k,0);
                        }
                }
            }
        
        for(int i=0;i<n;i++){
        
            for(int j=0;j<n;j++){
        
                if(ans[i][j])
                    cout << s[i][j];
                else
                    cout << "*";
            }
            cout << endl;
        }
        
        return 0;
    }