深度优先搜索——单词方阵

本文主要是介绍深度优先搜索——单词方阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

分析
逐个点逐个方向搜索，没什么难的，重点在于往某方向搜索时不能临时改变方向，即循环要在外面

#include <iostream>
#include <cstdio>
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);
}

这篇关于深度优先搜索——单词方阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---