单词方阵

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目链接

题目描述

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

单词方阵

输入输出格式

输入格式：

第一行输入一个数n。(7≤n≤100)。

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

输出格式：

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

解题思路：

也是dfs,(dfs大法好)，我们只要找到开头的y，然后dfs查找八个方向中下一个字母为i的方向(dfs的方向不变)，一直到终点即可。

这题关键还是我们要记录路径，也就是要记录我们走过的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

char str[100][100];
char s[9]={"yizhong"};
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八个方向
int vis[100][100];//标记路径
int n;

struct node{
    int x,y;
}c[100];//储存路径

void dfs(int x,int y,node c[],int k,int cur)
{
    if(cur==7){//找到完整的路径，标记
        for(int i=0;i<7;i++){
            vis[c[i].x][c[i].y]=1;
        }
    }
    else{
        int dx=x+dir[k][0];//根据前一个的方向继续寻找
        int dy=y+dir[k][1];
        if(cur==6||str[dx][dy]==s[cur+1]){
            c[cur].x=x;//存储前一个路径
            c[cur].y=y;
            dfs(dx,dy,c,k,cur+1);//dfs下一个字母
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>str[i][j];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(str[i][j]=='y'){
                for(int k=0;k<8;k++){
                    int x=i+dir[k][0];//沿着正确方向走
                    int y=j+dir[k][1];
                    if(str[x][y]=='i'){
                        dfs(i,j,c,k,0);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(vis[i][j]) printf("%c",str[i][j]);//代表我们走过的路径
            else printf("*");
        }
        printf("\n");
    }
    return 0;
}