10010 - Where's Waldorf?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: WA

Post by tan_Yui » Sat Jul 16, 2005 3:54 pm

Hi, Raj Ariyan, Chok. Try this input.

Input
1

10 7
aamacaa
aaacaaa
aaaapaa
hraGocL
aeaaoaa
vaLLLLa
ugLLraa
margorp
cARCfaa
aaaaaaa
9
acmuva
program
calloc
forLOOP
Hello
gram
log
arc
aaaa
Output should be :
10 1
8 7
9 1
9 5
4 1
8 4
6 6
9 2
1 6
Best regards.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

<>

Post by Raj Ariyan » Tue Jul 19, 2005 8:25 am

Hi tan_Yui,
Thanks for ur I/O. I'll check my code as soon as posible. Thanks again for ur great help.
Some Love Stories Live Forever ....

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Thanks

Post by Chok » Tue Jul 19, 2005 8:39 am

Hi Tan_Yui,
Many Many thanks for ur I/O.

liangchene
New poster
Posts: 12
Joined: Thu May 19, 2005 6:07 am

Post by liangchene » Thu Jan 26, 2006 9:00 pm

I keep getting wrong answers.
Is there any tricks to this problem?

all I did is go through all the points and search for all directions.

samiron
New poster
Posts: 4
Joined: Tue Sep 14, 2004 6:33 am

10010 getting WA !!!!help pls

Post by samiron » Sun Feb 05, 2006 8:35 am

hi,
i'm trying to solve the problem by checking from each position of the grid in eight directions. Starting from top-left corner and continuing the process horizontally when a match founds then the loops stops.

How can i pass the WA????
my code is as follows:

#include<stdio.h>
#include<string.h>
#include<ctype.h>


int hori[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int vert[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int len;
long t_case;
int m,n,i,p,a,b,j,xx,yy;
char mainGrid[55][55];
char str[20];


void Toupper(char ch[])
{
int i=0;
while(ch != NULL)
{
ch = toupper(ch);
i++;
}
}


int search(int x, int y, int dir_vert, int dir_hor)
{
int i,j,k=0;
int end_x=0;
int end_y=0;
if(dir_vert != 0)
end_x = x + ( len - 1 ) * dir_vert ;
if(dir_hor != 0)
end_y = y + ( len - 1 ) * dir_hor ;

i = x;
j = y;

if( end_x >= 0 && end_x < m && end_y >= 0 && end_y < n)
{
while(str[k] != NULL && str[k] == mainGrid[j] )
{
k++;
i = i + dir_vert;
j = j + dir_hor;
}
if(k == len)
return 1;
}
return 0;
}


int main()
{

//freopen("10010.in","r",stdin);
//freopen("10010.out","w",stdout);
scanf("%ld",&t_case);

while(t_case--)
{
scanf("%d%d",&m,&n);
for(i = 0 ; i < m ; i++)
{
scanf("%s",mainGrid);
Toupper(mainGrid);
}
scanf("%d",&p);
while(p--)
{
scanf("%s",str);
Toupper(str);
len = strlen(str);

for(a = 0 ; a < n ; a++)
{
for(b = 0 ; b < m ; b++)
{
for(j = 0 ; j<8 ; j++)
{
if(search(a, b, vert[j], hori[j]))
{
printf("%d %d\n", a+1,b+1);
a = n;
b = m;
j = 8;
}
}
}
}
}
if(t_case != 0)
printf("\n");

}


return 0;
}

:x
i am rony(nick name).i am student of cse in kuet.

airies
New poster
Posts: 2
Joined: Sun Mar 05, 2006 5:33 pm

10010--WA

Post by airies » Sun Mar 05, 2006 5:44 pm

I use java, and it always gets WA. Can anyone help me, find out the bug,or give me some special input to test, please? Or you have some idea about my code, please reply, thanks!

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();
       	}
    }
    
}

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Mar 06, 2006 5:26 am

I am not sure if that is the cause of the problem, but in my code I trimmed all the inputs. I haven't checked the rest of your code, that was the only thing I noticed right away.

In general, it is a good idea to trim the input when using Java, unless you need whitespace for some reason. scanf() just ignores whitespace, and UVa doesn't test with Java, so you can expect a lot of those things popping up. Oh, and blank lines.. they are killing me.

For that one I used the same ReadLn() that you are using, but since then I switched to this one:

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();
}
Well, it worked for me so far. Remove trim() in return when it's not needed.

Darko

[EDIT: Hm, I just noticed you are doing everything in the constructor. If nothing, it looks weird. I am not sure, but that might be the cause of your troubles]

airies
New poster
Posts: 2
Joined: Sun Mar 05, 2006 5:33 pm

Post by airies » Tue Mar 07, 2006 7:24 am

Thank for your reply! I will try your ReadLn code to test.
By the way, I rewrite this in c++ and it do work...

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

10010 W.A. Help Please

Post by N@$!M » Fri Jan 12, 2007 8:53 pm

Pleeeee...........ase Help me.
:roll:
I am getting WA in it.
Can Anyone give me some critical I/O Sets.?
Here Is My Code:

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]
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sat Jan 13, 2007 12:18 pm

First search your problem in the board.Dont open a new thread if there is one already. If there is no thread then open a new one.
form kisui na ... class tai asol....
iF U hv d class u get the form....

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Post by rhsumon » Fri Jan 11, 2008 4:40 pm

Hi all, I'm a new programmer -- i mean my code is alright but WA plz help me to find the simple bug that i cannot find................
My program gives above input as right... so what can i do plz help anyone....

Here is my code:

Code: Select all

What a silly mistake .... i did not see about the blank between two consicutive output.............
code Removed after ac..........
Plz help me ........... i'm boaring about this.......

shobhon
New poster
Posts: 1
Joined: Thu Aug 07, 2008 5:03 pm

10010 - Where's Waldorf?

Post by shobhon » Sat Jun 20, 2009 12:33 pm

i'm getting wa in 10010..:(
plz help..

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

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10010 - Where's Waldorf?

Post by Jehad Uddin » Mon Jul 27, 2009 7:03 pm

You r using so many getchar();why?? try to remove extra getchar() and also change it

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--;
to this one

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

meee...
New poster
Posts: 4
Joined: Tue Dec 09, 2008 4:04 pm

Re: 10010 - Where's Waldorf?

Post by meee... » Thu Oct 01, 2009 8:48 pm

HI

I got runtime Error , helpme plz , I'm novice
it's my code:

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;
}
thank u very much!!!

n1gr0
New poster
Posts: 1
Joined: Sun Oct 18, 2009 4:49 pm

Re: 10010 - Where's Waldorf?

Post by n1gr0 » Sun Oct 18, 2009 4:56 pm

hi there!
I think I've got a good solution too, however I'm getting WA too...
I checked the I/O of the other users of the board...and It passed correctly all so... I dont know...

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;

	}
}

Post Reply

Return to “Volume 100 (10000-10099)”