Input
Output should be :1
10 7
aamacaa
aaacaaa
aaaapaa
hraGocL
aeaaoaa
vaLLLLa
ugLLraa
margorp
cARCfaa
aaaaaaa
9
acmuva
program
calloc
forLOOP
Hello
gram
log
arc
aaaa
Best regards.10 1
8 7
9 1
9 5
4 1
8 4
6 6
9 2
1 6
Moderator: Board moderators
Output should be :1
10 7
aamacaa
aaacaaa
aaaapaa
hraGocL
aeaaoaa
vaLLLLa
ugLLraa
margorp
cARCfaa
aaaaaaa
9
acmuva
program
calloc
forLOOP
Hello
gram
log
arc
aaaa
Best regards.10 1
8 7
9 1
9 5
4 1
8 4
6 6
9 2
1 6
Code: Select all
import java.io.*;
import java.util.*;
class Main {
int m,n,k;
char[][] input;
String[] keyword;
StringTokenizer line;
static String ReadLn (int maxLg){
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try{
while (lg < maxLg){
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg-1));
}
catch (IOException e){
return (null);
}
}
public Main() throws Exception{
System.out.println();
line=new StringTokenizer(Main.ReadLn (255));
m=Integer.parseInt(line.nextToken());
n=Integer.parseInt(line.nextToken());
input=new char[m][n];
for(int i=0;i<m;i++){
input[i]=Main.ReadLn (255).toLowerCase().toCharArray();
}
k=Integer.parseInt(Main.ReadLn (255));
keyword=new String[k];
for(int i=0;i<k;i++){
keyword[i]=Main.ReadLn (255).toLowerCase();
}
}
public void search(){
for(int key=0;key<k;key++){
boolean find=false;
for(int i=0;i<m;i++)
{
String temp=new String(input[i]);
int start=-1;
while(true){
start=temp.indexOf(keyword[key].charAt(0),start+1);
if(start<0)
break;
if(trace(i, start, key)){
System.out.println((i+1)+" "+(start+1));
find=true;
break;
}
}
if(find)
break;
}
}
}
public boolean trace(int x,int y,int z){
int length=keyword[z].length();
int i=1;
if(length==1)
return true;
if(length<=(n-y)){
for(i=1;i<length;i++){
if(input[x][y+i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length<=(n-y) && length<=(m-x)){
for(i=1;i<length;i++){
if(input[x+i][y+i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length<=(m-x)){
for(i=1;i<length;i++){
if(input[x+i][y]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length<=(m-x) && length-1<=y){
for(i=1;i<length;i++){
if(input[x+i][y-i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length-1<=y){
for(i=1;i<length;i++){
if(input[x][y-i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length-1<=y && length-1<=x){
for(i=1;i<length;i++){
if(input[x-i][y-i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length-1<=x){
for(i=1;i<length;i++){
if(input[x-i][y]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
if(length-1<=x && length<=(n-y)){
for(i=1;i<length;i++){
if(input[x-i][y+i]!=keyword[z].charAt(i))
break;
if(i==length-1)
return true;
}
}
return false;
}
public static void main(String[] args) throws Exception{
int c=Integer.parseInt(Main.ReadLn (255));
Main[] work=new Main[c];
for(int i=0;i<c;i++)
work[i]=new Main();
for(int i=0;i<c;i++){
work[i].search();
if(i+1<c)
System.out.println();
}
}
}
Code: Select all
private String readLine() {
StringBuffer sb = new StringBuffer("");
int b = 0;
while (b != '\n' && b >= 0) {
try {
b = System.in.read();
} catch (IOException e) {
return null;
}
if (b != '\r' && b != '\n' && b >= 0)
sb.append((char) b);
}
if (sb.length() == 0 && b < 0)
return null;
return sb.toString().trim();
}
Code: Select all
#include<stdio.h>
#include<string.h>
struct point{
int x,y;
};
bool compare(char a,char b)
{
if(a>='A' && a<='Z'){
a=a+32;
}
if(b>='A' && b<='Z'){
b=b+32;
}
if(a==b) return true;
return false;
}
point find(char arr[][51],int r,int c,char word[])
{
int len,i,j,k,l,m;
bool flag;
point p;
len=strlen(word);
for(i=0;i<r;i++){
for(j=0;j<c;j++){
if(compare(word[0],arr[i][j])){
flag=true;
if(j<=c-len){
for(k=1,l=j+1;k<len;k++,l++){
if(!compare(word[k],arr[i][l])){
flag=false;
break;
}
}
}
else flag=false;
if(flag==true){
p.x=i+1;
p.y=j+1;
return p;
}
flag=true;
if(j>=len-1){
for(k=1,l=j-1;k<len;k++,l--){
if(!compare(word[k],arr[i][l])){
flag=false;
break;
}
}
}
else flag=false;
if(flag==true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(i>=len-1){
for(k=1,l=i-1;k<len;k++,l--){
if(!compare(word[k],arr[l][j])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(r-len>=i){
for(k=1,l=i+1;k<len;k++,l++){
if(!compare(word[k],arr[l][j])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(j<=c-len && i>=len-1){
for(k=1,l=i-1,m=j+1;k<len;k++,l--,m++){
if(!compare(word[k],arr[l][m])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(j>=len-1 && i>=len-1){
for(k=1,l=i-1,m=j-1;k<len;k++,l--,m--){
if(!compare(word[k],arr[l][m])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(j<=c-len && r-len>=i){
for(k=1,l=i+1,m=j+1;k<len;k++,l++,m++){
if(!compare(word[k],arr[l][m])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
flag = true;
if(j>=len-1 && r-len>=i){
for(k=1,l=i+1,m=j-1;k<len;k++,l++,m--){
if(!compare(word[k],arr[l][m])){
flag = false;
break;
}
}
}
else flag=false;
if(flag == true){
p.x=i+1;
p.y=j+1;
return p;
}
}
}
}
}
void main()
{ //freopen("10010.txt","r",stdin);
char arr[51][51],word[73],r,c,tc,n,i;
point p;
scanf("%d",&tc);
while(tc-->0){
scanf("%d%d",&r,&c);
for(i=0;i<r;i++){
scanf("%s",arr[i]);
}
scanf("%d",&n);
while(n-->0){
scanf("%s",word);
p=find(arr,r,c,word);
printf("%d %d\n",p.x,p.y);
}
printf("\n");
}
}
Code: Select all
What a silly mistake .... i did not see about the blank between two consicutive output.............
code Removed after ac..........
Code: Select all
#include<stdio.h>
#include<ctype.h>
#include<string.h>
char b[100],a[100][100];
int n,m;
bool check1(int i,int j)
{
int k;
for(k=0;a[i][j]&&b[k];j++,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check2(int i,int j)
{
int k;
for(k=0;j>=0&&b[k];j--,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check3(int i,int j)
{
int k;
for(k=0;i>=0&&b[k];i--,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check4(int i,int j)
{
int k;
for(k=0;i<n&&b[k];i++,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check5(int i,int j)
{
int k;
for(k=0;i<n&&a[i][j]&&b[k];i++,j++,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check6(int i,int j)
{
int k;
for(k=0;i>=0&&j>=0&&b[k];i--,j--,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check7(int i,int j)
{
int k;
for(k=0;i>=0&&a[i][j]&&b[k];i--,j++,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
bool check8(int i,int j)
{
int k;
for(k=0;i<n&&j>=0&&b[k];i++,j--,k++)
if(a[i][j]!=b[k])
return 0;
if(b[k]=='\0')
return 1;
else
return 0;
}
int main()
{
int i,j,k,t,flag,q;
scanf("%d",&t);
getchar();
getchar();
while(t>0)
{
scanf("%d%d",&n,&m);
getchar();
for(i=0;i<n;i++)
scanf("%s",a[i]);
for(i=0;i<n;i++)
for(j=0;a[i][j];j++)
a[i][j]=tolower(a[i][j]);
scanf("%d",&q);
getchar();
for(i=0;i<q;i++)
{
scanf("%s",b);
for(j=0;b[j];j++)
b[j]=tolower(b[j]);
for(j=0,flag=0;j<n;j++)
{
for(k=0;a[j][k];k++)
{
if(check1(j,k)||check2(j,k)||check3(j,k)||check4(j,k)||check5(j,k)||check6(j,k)||check7(j,k)||check8(j,k))
{
printf("%d %d\n",j+1,k+1);
if(t!=1)
printf("\n");
flag=1;
break;
}
}
if(flag)
break;
}
}
if(t!=1)
getchar();
t--;
}
return 0;
}
Code: Select all
for(j=0,flag=0;j<n;j++)
{
for(k=0;a[j][k];k++)
{
if(check1(j,k)||check2(j,k)||check3(j,k)||check4(j,k)||check5(j,k)||check6(j,k)||check7(j,k)||check8(j,k))
{
printf("%d %d\n",j+1,k+1);
if(t!=1)
printf("\n");
flag=1;
break;
}
}
if(flag)
break;
}
}
t--;
Code: Select all
for(j=0,flag=0;j<n;j++)
{
for(k=0;a[j][k];k++)
{
if(check1(j,k)||check2(j,k)||check3(j,k)||check4(j,k)||check5(j,k)||check6(j,k)||check7(j,k)||check8(j,k))
{
printf("%d %d\n",j+1,k+1);
flag=1;
break;
}
}
if(flag)
break;
}
}
if(t!=1)
printf("\n");
t--;
Code: Select all
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctype.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <map>
#include <locale>
#include <sstream>
#include <utility>
#include <limits>
#include <cctype>
//#include <fstream>
using namespace std;
bool horiz(char *word,char **matrix,int row,int col,int height,int width){
int i;
int right = col;
int left = col;
bool rpt_R = true;
bool rpt_L = true;
for(i = 0; i < strlen(word); i++){
if(left < 0){
rpt_L = false;
break;
}
if( word[i] != matrix[row][left--]){
rpt_L = false;
break;
}
}
for(i = 0; i < strlen(word); i++){
if(right >= width){
rpt_R = false;
break;
}
if(word[i] != matrix[row][right++]){
rpt_R = false;
break;
}
}
return (rpt_L || rpt_R);
}
bool vert(char *word,char **matrix,int row,int col,int height,int width){
int i;
int down = row;
int up = row;
bool rpt_D = true;
bool rpt_U = true;
for(i = 0; i < strlen(word); i++){
if(up < 0){
rpt_U = false;
break;
}
if( word[i] != matrix[up--][col]){
rpt_U = false;
break;
}
}
for(i = 0; i < strlen(word); i++){
if(down >= height){
rpt_D = false;
break;
}
if(word[i] != matrix[down++][col]){
rpt_D = false;
break;
}
}
return (rpt_U || rpt_D);
}
bool diag(char *word,char **matrix,int row,int col,int height,int width){
int i;
int right = col;
int left = col;
int up = row;
int down = row;
bool rpt_UR = true;
bool rpt_UL = true;
bool rpt_DR = true;
bool rpt_DL = true;
for(i = 0; i < strlen(word); i++){
if(down < 0 || left < 0){
rpt_DL = false;
break;
}
if( word[i] != matrix[down--][left--]){
rpt_DL = false;
break;
}
}
down = row;
left = col;
for(i = 0; i < strlen(word); i++){
if(up >= height || left < 0){
rpt_UL = false;
break;
}
if( word[i] != matrix[up++][left--]){
rpt_UL = false;
break;
}
}
up = row;
left = col;
for(i = 0; i < strlen(word); i++){
if(down < 0 || right >= width){
rpt_DR = false;
break;
}
if(word[i] != matrix[down--][right++]){
rpt_DR = false;
break;
}
}
down = row;
right = col;
for(i = 0; i < strlen(word); i++){
if(up >= height || right >= width ){
rpt_UR = false;
break;
}
if(word[i] != matrix[up++][right++]){
rpt_UR = false;
break;
}
}
return (rpt_DL || rpt_DR || rpt_UR || rpt_UL);
}
int main(){
int n,i,j,k,l,m;
int input;
int rows,cols;
int nMiss;
bool newLine=false;
scanf("%d",&n);
pair<int,int> *myPair;
while(n--){
char**matrix;
char *words;
if(newLine){
cout << endl;
}
newLine = true;
scanf("%d %d",&rows,&cols);
matrix = (char**)malloc(rows*sizeof(char*));
for(i = 0; i < rows; i++)
matrix[i] = (char*)malloc(sizeof(char)*cols);
for(i = 0; i < rows; i++)
cin >> matrix[i];
for(i = 0; i < rows; i++)
for(j = 0; j < cols; j++)
if(isupper(matrix[i][j]))
matrix[i][j] = tolower(matrix[i][j]);
scanf("%d",&nMiss);
int x,y;
for(i = 0;i < nMiss; i++){
x = numeric_limits<int>::max();
y = numeric_limits<int>::max();
words = (char*)malloc(sizeof(char)*(rows*cols));
scanf("%s",words);
for(j = 0; j < strlen(words); j++)
if(isupper(words[j]))
words[j] = tolower(words[j]);
for(j = 0; j < rows; j++){
for(k = 0; k < cols; k++){
if(horiz(words,matrix,j,k,rows,cols) || diag(words,matrix,j,k,rows,cols)
|| vert(words,matrix,j,k,rows,cols)){
if(j < x){
x = j;
y = k;
}
else if(j == x && k < y){
x = j;
y = k;
}
}
}
}
cout << x+1 << " " << y+1 << endl;
free(words);
}
for(i = 0; i < rows; i++)
free(matrix[i]);
free(matrix);
}
return 0;
}
Code: Select all
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
private static int numLetrasPosibles = 28;
private static char[][] tabla;
private static int m = 0;
private static int n = 0;
private static String[] palabras;
private static ArrayList<Integer>[] posicionesPorLetra = new ArrayList[numLetrasPosibles];
/**
* Método inicial.
*
* @param args
* argumentos.
* @throws IOException
* si falla.
*/
public static void main(String[] args) throws IOException {
// Scanner para la entrada.
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(
System.in)));
int numCasos = leerNum(in);
// Para cada caso
for (int i = 0; i < numCasos; i++) {
// linea en blanco
in.nextLine().split(" ");
// leo m y x.
int[] tamanyo = leer2Num(in);
m = tamanyo[0];
n = tamanyo[1];
// inicializar la tabla
tabla = new char[m][n];
// leo la tabla.
leerTabla();
// inicializar array
inicializarPoscionesPorLetra();
// Inicializo las posiciones en que aparece cada caracter.
inicializarCuentas();
// leer num palabras
int numPalabras = leerNum(in);
// inicializo array de palabras.
palabras = new String[numPalabras];
// leer las palabras
for (int k = 0; k < numPalabras; k++) {
String palabraKesima = readLine();
palabraKesima = palabraKesima.toLowerCase();
palabras[k] = palabraKesima;
}
// buscar
// para cada palabra
for (int k = 0; k < numPalabras; k++) {
char[] palabra = palabras[k].toCharArray();
// para cada posicion que está laprimera letra
Iterator<Integer> it = posicionesPorLetra[(int) palabra[0] - 97]
.iterator();
// sobraría xk siempre está la palabra
// tener k buskar..
while (it.hasNext()) {
int fila = ((Integer) (it.next())).intValue();
int columna = ((Integer) (it.next())).intValue();
int[] valido = null;
if (palabra.length > 1) {
valido = buscar(palabra, fila, columna);
}else{
valido[0]=fila;
valido[1]=columna;
}
// si valido entonces salir
if (valido[0] != -1 && valido[1] != -1) {
valido[0]++;
valido[1]++;
System.out.println(valido[0] + " " + valido[1]);
break;
}
}
}
if (numCasos > 1) {
System.out.println("");
}
}
}
private static int[] buscar(char[] palabra, int fila, int columna) {
int[] num = { -1, -1 };
int i, j = 0;
i = fila;
j = columna;
boolean encontrado = true;
// buscar hacia la derecha
encontrado = true;
j = columna;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (j + 1 > n - 1) {
encontrado = false;
break;
}
if (palabra[k] != tabla[i][++j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar diagonal bajando hacia derecha
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i + 1 > m - 1 || j + 1 > n - 1) {
encontrado = false;
break;
}
if (palabra[k] != tabla[++i][++j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar hacia abajo
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i + 1 > m - 1) {
encontrado = false;
break;
}
if (palabra[k] != tabla[++i][j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar diagonal bajando hacia izq
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i + 1 > m - 1 || j - 1 < 0) {
encontrado = false;
break;
}
if (palabra[k] != tabla[++i][--j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar hacia la izq
encontrado = true;
i = fila;
j = columna;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (j - 1 < 0) {
encontrado = false;
break;
}
if (palabra[k] != tabla[i][--j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar diagonal subiendo hacia izq
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i - 1 < 0 || j - 1 < 0) {
encontrado = false;
break;
}
if (palabra[k] != tabla[--i][--j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar hacia arriba
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i - 1 < 0) {
encontrado = false;
break;
}
if (palabra[k] != tabla[--i][j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
// buscar diagonal subiendo hacia derecha
encontrado = true;
j = columna;
i = fila;
for (int k = 1; k < palabra.length; k++) {
// Para que no se salga buscando..
if (i - 1 < 0 || j + 1 > n - 1) {
encontrado = false;
break;
}
if (palabra[k] != tabla[--i][++j]) {
encontrado = false;
break;
}
}
if (true == encontrado) {
num[0] = fila;
num[1] = columna;
return num;
}
return num;
}
private static String readLine() {
StringBuffer sb = new StringBuffer("");
int b = 0;
while (b != '\n' && b >= 0) {
try {
b = System.in.read();
} catch (IOException e) {
return null;
}
if (b != '\r' && b != '\n' && b >= 0)
sb.append((char) b);
}
if (sb.length() == 0 && b < 0)
return null;
return sb.toString().trim();
}
/**
* Inicializa posicionesPorLetra.
*
* @param m
* filas de la tabla.
* @param n
* columnas de la tabla.
*/
private static void inicializarCuentas() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
posicionesPorLetra[(int) tabla[i][j] - 97].add(i);
posicionesPorLetra[(int) tabla[i][j] - 97].add(j);
}
}
}
/**
* Lee de fila en fila la tabla.
*
* @param m
* filas.
*/
private static void leerTabla() {
// leer la matriz
for (int k = 0; k < m; k++) {
String filaKesima = readLine();
filaKesima = filaKesima.toLowerCase();
// guardarlo en un array...
tabla[k] = filaKesima.toCharArray();
}
}
/**
* Inicializa el array de posicionesPorLetra.
*/
private static void inicializarPoscionesPorLetra() {
for (int k = 0; k < numLetrasPosibles; k++) {
posicionesPorLetra[k] = new ArrayList<Integer>();
}
}
private static int leerNum(Scanner in) {
String[] numeros = in.nextLine().split(" ");
int index = 0;
int num = 0;
for (; index < numeros.length; index++) {
try {
num = Integer.parseInt(numeros[index]);
break;
} catch (final NumberFormatException e) {
// Si falla.
}
}
return num;
}
private static int[] leer2Num(Scanner in) {
int[] num = { 0, 0 };
String[] numeros;
// leo m y n
numeros = in.nextLine().split(" ");
int index = 0;
int m = 0;
for (; index < numeros.length; index++) {
try {
m = Integer.parseInt(numeros[index]);
break;
} catch (final NumberFormatException e) {
// Si falla.
}
}
index++;
int n = 0;
for (; index < numeros.length; index++) {
try {
n = Integer.parseInt(numeros[index]);
break;
} catch (final NumberFormatException e) {
// Si falla.
}
}
num[0] = m;
num[1] = n;
return num;
}
}