洛谷[P1101 单词方阵] {搜索|DFS}
解题思路
1、首先找到字符’y’的坐标，然后在对于每一个方向（共有八个方向）进行搜索，这样可以保证搜索到的字符串是在一个方向上。
2、然后设定一个字符数组c用来存储给定的字符串并且用来比较搜索到的字符是不是对应相等。
3、使用roadx、roady数组来记录走过的路径，注意处理最初的路径('y’的坐标)。
4、一旦下标等于7，说明搜索的该方向可以完美形成“yizhong”，将路径上所有的点的b数组对应设置为1（方便输出）即可。
完整代码
#include<bits/stdc++.h>
using namespace std
;
char a
[110][110];
int b
[110][110];
char c
[7]={'y','i','z','h','o','n','g'};
int M
;
int x
[9]={0,0,1,1,1,0,-1,-1,-1};
int y
[9]={0,1,1,0,-1,-1,-1,0,1};
int roadx
[7];
int roady
[7];
void dfs(int num
,int p
,int q
,int rode
)
{
if(num
==7)
{
for(int i
=0;i
<7;i
++)
{
b
[roadx
[i
]][roady
[i
]]=1;
}
return ;
}
if(num
==1)
{
roadx
[0]=p
;
roady
[0]=q
;
}
int xa
=p
+x
[rode
];
int ya
=q
+y
[rode
];
if(xa
>=0&&xa
<M
&&ya
>=0&&ya
<M
&&a
[xa
][ya
]==c
[num
])
{
roadx
[num
]=xa
;
roady
[num
]=ya
;
dfs(num
+1,xa
,ya
,rode
);
}
}
int main()
{
scanf("%d",&M
);
for(int i
=0;i
<M
;i
++)
{
scanf("%s",a
[i
]);
}
for(int i
=0;i
<M
;i
++)
{
for(int j
=0;j
<M
;j
++)
{
if(a
[i
][j
]=='y')
{
for(int n
=1;n
<=8;n
++)
{
dfs(1,i
,j
,n
);
}
}
}
}
for(int i
=0;i
<M
;i
++)
{
for(int j
=0;j
<M
;j
++)
{
if(b
[i
][j
]==1)
{
printf("%c",a
[i
][j
]);
}
else printf("*");
}
printf("\n");
}
return 0;
}
