题:http://acm.sdibt.edu.cn/vjudge/contest/view.action?cid=2121#problem/I
3 april purple quilt
5
rprit
ahqln
ietep
zrysg
ogwey
3
pel aup bcr
0
一道把老子你弄得死去活来的题(只是因为自己菜)
题意:
先给你n个串,然后给个t×t的表,从表中遍历找寻这n个串,如果有就输出这个串,其中表中的q只能当作qu。
这个题我真的服了,对搜索的理解还是不到位,dfs里的return 不是结束条件,另外搜索不到你原先的标记要清零,t的原因是因为你会把所有的情况遍历? 好多好多
看代码把
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std;
string s[500];
char a[10][10];
int vis[10][10];
bool flag[1000];
int n;
int f[8][2]= {{1,0},{-1,0},{0,1},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
void dfs(int x,int y,int k,int ge)
{
vis[x][y]=1;
if(flag[k]==1) // 没有这个if的话,当你条件成立,你会继续搜索他的上一层。比如这个字母的上下左右都是a,你上是a,你不会接着停止,而是搜索别的可能,会耗时间长。
return ;
if(s[k][ge]==‘q‘)
if(s[k][ge+1]==‘u‘)
ge+=1;
else
return ;
if(ge==s[k].size()-1)
{
flag[k]=1;
return ;
}
for(int i=0; i<=7; i++)
{
int xx=f[i][0]+x;
int yy=f[i][1]+y;
if(vis[xx][yy]==0&&xx>=0&&xx<=n-1&&yy>=0&&yy<=n-1&&a[xx][yy]==s[k][ge+1])
{
dfs(xx,yy,k,ge+1);
}
}
vis[x][y]=0;
return ;
}
int main()
{
int t,i,chu,j,k;
cin>>t;
for(i=0; i<=t-1; i++)
cin>>s[i];
sort(s,s+t);
while(cin>>n&&n)
{
for(i=0; i<=n-1; i++)
{
for(j=0; j<=n-1; j++)
cin>>a[i][j];
}
for(i=0; i<=t-1; i++)
{
chu=0;
int zz=0;
memset(flag,0,sizeof(flag));
for(j=0; j<=n-1; j++)
{
for(k=0; k<=n-1; k++)
{
memset(vis,0,sizeof(vis));
if(a[j][k]==s[i][0])
{
zz++;
dfs(j,k,i,0);
if(flag[i]==1)
{
chu=1;
cout<<s[i]<<endl;
break;
}
}
}
if(chu==1)
{
break;
}
}
}
cout<<"-"<<endl;
}
return 0;
}
原文:https://www.cnblogs.com/bhd123/p/10004035.html