#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