#include <iostream>
using namespace std;
int m,n;
string abuscar;
int tamcad;
bool buscarH(int f,int c, string mapa[])
{
//derecha
int fin = c+tamcad-1;
if(fin<n)
{
int i,j;
for(i = c,j=0 ; i<=fin ; i++,j++)
if(abuscar[j]!=mapa[f][i])
break;
if(i-1 == fin)
return true;
}
//izquierda
fin = c-tamcad+1;
if(fin>=0)
{
int i,j;
for(i = c,j=0 ; i>=fin ; i--,j++)
if(abuscar[j]!=mapa[f][i])
break;
if(i+1 == fin)
return true;
}
return false;
}
bool buscarV(int f,int c, string mapa[])
{
//abajo
int fin = f+tamcad-1;
if(fin<m)
{
int i,j;
for(i = f,j=0 ; i<=fin ; i++,j++)
if(abuscar[j]!=mapa[i][c])
break;
if(i-1 == fin)
return true;
}
//arriba
fin = f-tamcad+1;
if(fin>=0)
{
int i,j;
for(i = f,j=0 ; i>=fin ; i--,j++)
if(abuscar[j]!=mapa[i][c])
break;
if(i+1 == fin)
return true;
}
return false;
}
bool buscarS(int f,int c, string mapa[])
{
//derecha y arriba
int finh = c+tamcad-1;
int finv = f-tamcad+1;
if(finh<n && finv>=0 )
{
int i,j,k;
for(i = c,k = f,j=0 ; i<=finh && k>=finv ; i++,j++,k--)
if(abuscar[j]!=mapa[k][i])
break;
if(i-1 == finh && k+1==finv)
return true;
}
//izquierda y abajo
finh = c-tamcad+1;
finv = f+tamcad-1;
if(finh>=0 && finv<m)
{
int i,j,k;
for(i = c,j=0, k=f ; i>=finh && k<=finv; i--,j++,k++)
if(abuscar[j]!=mapa[k][i])
break;
if(i+1 == finh && k-1==finv)
return true;
}
return false;
}
bool buscarB(int f,int c, string mapa[])
{
//derecha y abajo
int finh = c+tamcad-1;
int finv = f+tamcad-1;
if(finh<n && finv<m)
{
int i,j,k;
for(i = c,j=0,k=f ; i<=finh & k<=finv; i++,j++,k++)
if(abuscar[j]!=mapa[k][i])
break;
if(i-1 == finh && k-1==finv)
return true;
}
//izquierda y arriba
finh = c-tamcad+1;
finv = f-tamcad+1;
if(finh>=0 && finv>=0)
{
int i,j,k;
for(i = c,j=0,k=f ; i>=finh && k>=finv ; i--,j++,k--)
if(abuscar[j]!=mapa[k][i])
break;
if(i+1 == finh && k+1==finv)
return true;
}
return false;
}
void buscar(string mapa[])
{
int i,j;
for(i=0; i < m; i++)
for(j = 0; j < n; j++)
if(buscarH(i,j,mapa) || buscarV(i,j,mapa) || buscarS(i,j,mapa) || buscarB(i,j,mapa))
{
cout << i+1<<" "<<j+1<<endl;
return;
}
}
int main()
{
int casos,i,j,cb;
cin>>casos;
while(casos--)
{
cin >> m>>n;
string mapa[m];
for(i = 0; i<m; i++)
cin>>mapa[i];
for(i=0; i < m; i++)
for(j = 0; j < n; j++)
mapa[i][j] &= 95;
cin>>cb;
while(cb--)
{
cin>>abuscar;
tamcad = abuscar.size();
for(i=0; i < tamcad; i++)
abuscar[i] &= 95;
buscar(mapa);
}
if(casos>0)
cout << endl;
}
return 0;
}
jueves, 12 de abril de 2012
UVa - 10010 Where's Waldorf?
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario