深度优先搜索——单词方阵
洛谷 P1101 单词方阵
题目描述
给一nXn的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用“*”代替，以突出显示单词。
【深度优先搜索——单词方阵】分析
逐个点逐个方向搜索，没什么难的，重点在于往某方向搜索时不能临时改变方向，即循环要在外面
#include
#include
using namespace std;
char a[101][101],c[8]="yizhong";
bool b[101][101],p;
int n,i,j,k,s;
void dfs(int x,int y,int w)
{
if (s==6)
{
p=true;
b[x][y]=true;
return;
}
s++;
if (w==1&x+1<=n&a[x+1][y]==c[s]) dfs(x+1,y,w);
if (w==2&x-1>=1&a[x-1][y]==c[s]) dfs(x-1,y,w);
if (w==3&y+1<=n&a[x][y+1]==c[s]) dfs(x,y+1,w);
if (w==4&y-1>=1&a[x][y-1]==c[s]) dfs(x,y-1,w);
if (w==5&x+1<=n&y+1<=n&a[x+1][y+1]==c[s]) dfs(x+1,y+1,w);
if (w==6&x+1<=n&y-1>=1&a[x+1][y-1]==c[s]) dfs(x+1,y-1,w);
if (w==7&x-1>=1&y+1<=n&a[x-1][y+1]==c[s]) dfs(x-1,y+1,w);
if (w==8&x-1>=1&y-1>=1&a[x-1][y-1]==c[s]) dfs(x-1,y-1,w);
if (p) b[x][y]=true;
s--;
}
int main()
{
scanf("%d",&n);
for (i=1;
i<=n;
i++)
for (j=1;
j<=n;
j++)
cin>>a[i][j];
for (i=1;
i<=n;
i++)
for (j=1;
j<=n;
j++)
if (a[i][j]=='y')
for (k=1;
k<=8;
k++)
{
s=0;
p=false;
dfs(i,j,k);
}
for (i=1;
i<=n;
i++)
{
for (j=1;
j<=n;
j++)
if (b[i][j]) printf("%c",a[i][j]);
else printf("%c",'*');
printf("\n");
}
return(0);
} 推荐阅读
- 【译】20个更有效地使用谷歌搜索的技巧
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 富裕的好处是对资源的优先占有
- 深度解读（《秘密》（八）—健康的秘密）
- 影响深度思考的9种思维定式
- locate搜索
- springboot结合redis实现搜索栏热搜功能及文字过滤
- 茶事|茶事 | 单丛里的一泡奇葩
- Pytorch学习|sklearn-SVM 模型保存、交叉验证与网格搜索
- 为Google|为Google Cloud配置深度学习环境（CUDA、cuDNN、Tensorflow2、VScode远程ssh等）