【搜索】洛谷 P1101 单词方阵

题目描述

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

输入输出格式

输入格式： 第一行输入一个数n。(7<=n<=100)。

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

输出格式： 突出显示单词的nXn矩阵。

输入输出样例

输入样例#1： 7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa 输出样例#1：

代码

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n; char a[101][101],b[101][101],t[8]={' ','y','i','z','h','o','n','g'}; bool flag; void dfs(int x,int y) { if(x-6>=1&&y+6<=n) { for(int i=1;i<=7;i++)if(a[x-i+1][y+i-1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x-i+1][y+i-1]=t[i]; flag=0; } if(y+6<=n) { for(int i=1;i<=7;i++)if(a[x][y+i-1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x][y+i-1]=t[i]; flag=0; } if(x+6<=n&&y+6<=n) { for(int i=1;i<=7;i++)if(a[x+i-1][y+i-1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x+i-1][y+i-1]=t[i]; flag=0; } if(x+6<=n) { for(int i=1;i<=7;i++)if(a[x+i-1][y]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x+i-1][y]=t[i]; flag=0; } if(x+6<=n&&y-6>=1) { for(int i=1;i<=7;i++)if(a[x+i-1][y-i+1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x+i-1][y-i+1]=t[i]; flag=0; } if(y-6>=1) { for(int i=1;i<=7;i++)if(a[x][y-i+1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x][y-i+1]=t[i]; flag=0; } if(x-6>=1&&y-6>=1) { for(int i=1;i<=7;i++)if(a[x-i+1][y-i+1]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x+i-1][y-i+1]=t[i]; flag=0; } if(x-6>=1) { for(int i=1;i<=7;i++)if(a[x-i+1][y]!=t[i])flag=1; if(flag==0)for(int i=1;i<=7;i++)b[x-i+1][y]=t[i]; flag=0; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]='*'; for(int i=1;i<=n;i++)scanf("%s",a[i]+1); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dfs(i,j); for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)printf("%c",b[i][j]); return 0; }