Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct point
  6. {
  7.     int x,y;
  8. };
  9.  
  10. char str[52][52];
  11.  
  12. string q;
  13.  
  14. int n,m;
  15.  
  16. bool bfs(point ind,int X,int Y)
  17. {
  18.     queue<point>Q;
  19.  
  20.     point dir;
  21.  
  22.     dir.x = X;
  23.  
  24.     dir.y = Y;
  25.  
  26.     Q.push(ind);
  27.  
  28.     int l = 1;
  29.  
  30.     while(!Q.empty() && l<q.length())
  31.     {
  32.         point u = Q.front();
  33.  
  34.         Q.pop();
  35.  
  36.         point v;
  37.  
  38.         v.x = u.x+dir.x;
  39.  
  40.         v.y = u.y+dir.y;
  41.  
  42.         if(v.x>=0 && v.y>=0 && v.x<m && v.y<n && q[l]==str[v.x][v.y])
  43.         {
  44.             Q.push(v);
  45.  
  46.             l++;
  47.         }
  48.     }
  49.  
  50.     if(l==q.length())
  51.         return true;
  52.  
  53.     return false;
  54. }
  55.  
  56. int main()
  57. {
  58.  
  59.     int tc,test,i,j,k,l,t,len;
  60.  
  61.     scanf("%d",&test);
  62.  
  63.     for(tc=1; tc<=test; tc++)
  64.     {
  65.         scanf("%d%d",&m,&n);
  66.  
  67.         getchar();
  68.  
  69.         for(i=0; i<m; i++)
  70.         {
  71.             gets(str[i]);
  72.  
  73.             len = strlen(str[i]);
  74.  
  75.             for(j=0; j<len; j++)
  76.             {
  77.                 if(isupper(str[i][j]))
  78.                 {
  79.                     str[i][j] = tolower(str[i][j]);
  80.                 }
  81.             }
  82.         }
  83.  
  84.         scanf("%d",&t);
  85.  
  86.         getchar();
  87.  
  88.         for(i=1; i<=t; i++)
  89.         {
  90.             cin>>q;
  91.  
  92.             transform(q.begin(),q.end(),q.begin(),::tolower);
  93.  
  94.             bool dhukse = false;
  95.  
  96.             for(k=0; k<m; k++)
  97.             {
  98.                 for(l=0; l<n; l++)
  99.                 {
  100.                     if(q[0]==str[k][l])
  101.                     {
  102.                         point ind;
  103.                         ind.x = k;
  104.                         ind.y = l;
  105.  
  106.                         if(bfs(ind,1,1)||bfs(ind,0,1)||bfs(ind,1,0)||bfs(ind,1,-1)||bfs(ind,0,-1)||bfs(ind,-1,0)||bfs(ind,-1,1)||bfs(ind,-1,-1))
  107.                         {
  108.                             printf("%d %d\n",k+1,l+1);
  109.                             dhukse = true;
  110.                             break;
  111.                         }
  112.                     }
  113.                 }
  114.  
  115.                 if(dhukse)
  116.                 {
  117.                     break;
  118.                 }
  119.             }
  120.         }
  121.  
  122.         if(tc<test)
  123.         {
  124.             puts("");
  125.         }
  126.     }
  127.  
  128.     return 0;
  129. }