题目描述
给一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,(1007≤n≤100)。
第二行开始输入n×n的字母矩阵。
输出格式：
突出显示单词的n×n矩阵。
样例#1：
输入：
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
输出：
*******
*******
*******
*******
*******
*******
******* 样例#2：
输入：
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
输出：
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g
分析：
这道题挺有趣的我可能写的大部分都是模拟的代码,就是敲的有点烦.
这道题挺有趣的我可能写的大部分都是模拟的代码,就是敲的有点烦.
正解,有题目我们可以得知我们要求连续的字符串"yizhong",且组成字符串的字母的顺序不可改变,搜索该怎么搜?
因此我们必须确定搜索方向我们可以发现当我们知道字母'y'和字母'i'时我们就可以确定搜索的方向了想到这里这题就很简单了,
剩下的字母我们就可以用一个循环来依次找到.
输出的处理,因为题目要求只输出合格的字符串剩下的仅输出'*'那么我们可以用一个bool型变量judge[i][j]来判断如果它是合格的就赋值为true
否则赋值为false接下来判断一下是否合格就可以输出了
代码：
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int N=+;
char Map[N][N],keay[N][N];
int startx,starty,n;
int dirx[]={,,-,,,-,,-};//八个方向
int diry[]={,,,-,,,-,-};
bool judge[N][N];
void color(int ,int ,int );
void direct(int, int ,int );
void dfs(int x,int y)
{
for(int i=;i<;i++)
{
int xx=dirx[i]+startx;
int yy=diry[i]+starty;
if(xx<||xx>n||yy<||yy>n) continue;//边界
if(Map[xx][yy]=='i')//找'i'
{
direct(xx,yy,i);
}
}
}
void direct(int x,int y,int f)//f为这个字符串的方向
{
int xx=x,yy=y;
int cnt=;
for(int i=;i<=;i++)//因为只剩下5个没有找到的字母所以只用循环5次
{
xx=xx+dirx[f];
yy=yy+diry[f];
if(i==)
{
if(Map[xx][yy]=='z')
cnt++;
}
if(i==)
{
if(Map[xx][yy]=='h')
cnt++;
}
if(i==)
{
if(Map[xx][yy]=='o')
cnt++;
}
if(i==)
{
if(Map[xx][yy]=='n')
cnt++;
}
if(i==)
{
if(Map[xx][yy]=='g')
cnt++;
}
if(cnt==)
color(xx,yy,f);
}
return;
}
void color(int x,int y,int f)//赋值操作
{
int xx=x;
int yy=y;
judge[x][y]=true;
for(int i=;i<=;i++)//倒着回去赋值
{
xx=xx-dirx[f];
yy=yy-diry[f];
judge[xx][yy]=true;
}
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>Map[i][j];
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(Map[i][j]=='y')
{
startx=i;starty=j;
dfs(startx,starty);
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(judge[i][j])
cout<<Map[i][j];
else
cout<<"*";
}
cout<<endl;
}
return ;
}