错了20多遍做了n天的搜索！！-白红宇

错了20多遍做了n天的搜索！！

阅读量：4554 次

发布时间：2019-06-08

本文共 1520 字，大约阅读时间需要 5 分钟。

题：http://acm.sdibt.edu.cn/vjudge/contest/view.action?cid=2121#problem/I

3 april purple quilt

rprit

ahqln

ietep

zrysg

ogwey

pel aup bcr

一道把老子你弄得死去活来的题（只是因为自己菜）

题意：

先给你n个串，然后给个t×t的表，从表中遍历找寻这n个串，如果有就输出这个串，其中表中的q只能当作qu。

这个题我真的服了，对搜索的理解还是不到位，dfs里的return 不是结束条件，另外搜索不到你原先的标记要清零，t的原因是因为你会把所有的情况遍历？好多好多

看代码把

#include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           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<
            
             <