jueves, 12 de abril de 2012

UVa - 10010 Where's Waldorf?

#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;
}

No hay comentarios:

Publicar un comentario