422 - Word-Search Wonder

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

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

422

Post by htl » Tue Jul 23, 2002 1:48 pm

Why does this code get RE? And I don't exactly know that "Words may not ``wrap around'' rows or columns" means. ONLY horizontal and diagonal words proceed from right to left?
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
#define MIN(a,b) ((a)<=(b) ? (a) : (b))
#define ABS(a,b) ((a)<=(b) ? (b)-(a) : (a)-(b))
void main(void)
{
int n,x,len,y,found,z,ansx1,ansy1,ansx2,ansy2,a,b,c;
char data[100][101],s[101];
scanf("%d",&n);
for(x=0;x<n;x++)
scanf("%s",data[x]);
while(1)
{
scanf("%s",s);
if(s[0]=='0')
break;
len=strlen(s);
found=NO;
for(x=0;x<n && !found;x++)
for(y=0;y<=n-len && !found;y++)
{
for(z=0;z<len;z++)
if(s[z]!=data[x][y+z])
break;
if(z==len)
{
found=YES;
ansx1=x+1,ansy1=y+1;
ansx2=x+1,ansy2=y+len;
}
for(z=0;z<len && !found;z++)
if(s[len-z-1]!=data[x][y+z])
break;
if(z==len)
{
found=YES;
ansx1=x+1,ansy1=y+len;
ansx2=x+1,ansy2=y+1;
}
}
for(x=0;x<n && !found;x++)
for(y=0;y<=n-len && !found;y++)
{
for(z=0;z<len;z++)
if(s[z]!=data[y+z][x])
break;
if(z==len)
{
found=YES;
ansx1=y+1,ansy1=x+1;
ansx2=y+len,ansy2=x+1;
}
}
for(x=0;x<2*n-1 && !found;x++)
{
if(x<=n)
y=0,z=3-x;
else
y=x-3,z=0;
c=MIN(n-y,n-z);
if(len>c)
continue;
for(b=0;b<c-len+1 && !found;b++,y++,z++)
{
for(a=0;a<len;a++)
if(s[a]!=data[y+a][z+a])
break;
if(a==len)
{
found=YES;
ansx1=y+1,ansy1=z+1;
ansx2=y+len,ansy2=z+len;
}
for(a=0;a<len && !found;a++)
if(s[len-a-1]!=data[y+a][z+a])
break;
if(a==len)
{
found=YES;
ansx1=y+len,ansy1=z+len;
ansx2=y+1,ansy2=z+1;
}
}
}
for(x=0;x<2*n-1 && !found;x++)
{
if(x<n)
y=0,z=x;
else
y=x-3,z=3;
c=ABS(y,z);
if(len>c+1)
continue;
for(b=0;b<c-len+2 && !found;b++,y++,z--)
{
for(a=0;a<len;a++)
if(s[a]!=data[y+a][z-a])
break;
if(a==len)
{
found=YES;
ansx1=y+1,ansy1=z+1;
ansx2=y+len,ansy2=z-len+1;
}
for(a=0;a<len && !found;a++)
if(s[len-a-1]!=data[y+a][z-a])
break;
if(a==len)
{
found=YES;
ansx1=y+len,ansy1=z-len+1;
ansx2=y+1,ansy2=z+1;
}
}
}
if(!found)
printf("Not found\n");
else
printf("%d,%d %d,%d\n",ansx1,ansy1,ansx2,ansy2);
}
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Tue Jul 23, 2002 5:32 pm

Uh...I made an embarrassing mistake... I replaced the '3' with 'n-1' and got accepted.

Thiago Serra
New poster
Posts: 3
Joined: Sun Oct 05, 2003 1:32 pm
Location: Campinas-SP
Contact:

422 ???????????????????????????????????????????? 422

Post by Thiago Serra » Sat Jul 31, 2004 4:12 pm

In which directions should I consider to get ACC?
"Dust in the wind... Everything is dust in the wind"(Kansas)
"Hay que endurecer, pero sin perder la ternura jamas!"(Che Guevara)

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

422 - Word-Search Wonder

Post by CodeMaker » Mon Jan 17, 2005 6:01 pm

Hi, can anyone give me some I/O dataset for this problem, I have got WA and couldn't find out the problem in my code......plz help :cry:

here is my code in case u want to see......

Code: Select all

#include<stdio.h>
#include<string.h>
#define MAXSIZE 100

char matrix[MAXSIZE+1][MAXSIZE+1];
int r1,c1,r2,c2;

int check(char string[110],int size)
{
	int i,j,k,flage=0,len=strlen(string);
	int count_d,count_h,count_v;
	char inverse[110];

	j=0;
	for(i=len-1;i>=0;i--)
	{
		inverse[j++]=string[i];
	}

	count_d=count_h=count_v=0;
	for(i=1;i<=size-len+1;i++)
	{
		for(j=1;j<=size-len+1;j++)
		{
			if(matrix[i][j]==string[0])
			{
				for(k=1;string[k];k++)
				{
					if(matrix[i+k][j+k]==string[k])
						count_d++;
				}
				if(count_d==len-1)
				{
					r1=i;
					c1=j;
					r2=i+len-1;
					c2=j+len-1;
					flage=1;
				}
			}
			if(!flage && inverse[0]==matrix[i][j])
			{
				count_d=0;
				for(k=1;k<len;k++)
				{
					if(matrix[i+k][j+k]==inverse[k])
						count_d++;
				}
				if(count_d==len-1)
				{
					r2=i;
					c2=j;
					r1=i+len-1;
					c1=j+len-1;
					flage=1;
				}
			}
			if(flage)
				break;
		}
		if(flage)
			break;
	}
	if(!flage)
	{
		for(i=1;i<=size-len+1;i++)
		{
			for(j=1;j<=size;j++)
			{
				if(matrix[i][j]==string[0])
				{
					for(k=1;string[k];k++)
					{
						if(matrix[i+k][j]==string[k])
							count_v++;
					}
					if(count_v==len-1)
					{
						r1=i;
						c1=j;
						r2=i+len-1;
						c2=j;
						flage=1;
					}
				}
				if(flage)
					break;
			}
			if(flage)
				break;
		}
		for(i=1;i<=size;i++)
		{
			for(j=1;j<=size-len+1;j++)
			{
				if(matrix[i][j]==string[0])
				{
					for(k=1;string[k];k++)
					{
						if(matrix[i][j+k]==string[k])
							count_h++;
					}
					if(count_h==len-1)
					{
						r1=i;
						c1=j;
						r2=i;
						c2=j+len-1;
						flage=1;
					}
				}
				if(!flage && inverse[0]==matrix[i][j])
				{
					count_h=0;
					for(k=1;k<len;k++)
					{
						if(matrix[i][j+k]==inverse[k])
							count_h++;
					}
					if(count_h==len-1)
					{
						r2=i;
						c2=j;
						r1=i;
						c1=j+len-1;
						flage=1;
					}
				}
				if(flage)
					break;
			}
			if(flage)
				break;
		}
	}
	return flage;
}

void main()
{
	int size,i,j;
	char string[110];
//	freopen("in.in","r",stdin);

	while(scanf("%d",&size)==1) 
	{
		for(i=1;i<=size;i++)
		{
			getchar();
			for(j=1;j<=size;j++)
			{
				scanf("%c",&matrix[i][j]);
			}
		}
		getchar();
		while(gets(string) && strcmp(string,"0"))
		{
			if(check(string,size))
				printf("%d,%d %d,%d\n",r1,c1,r2,c2);
			else
				printf("Not found\n");
		}
	}
}
[/code]
Jalal : AIUB SPARKS

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 15, 2005 10:57 pm

I solved it long time ago. So I have forgot the restrictions. But you can try the input output set. Your code returns wrong answer for the set.

Input:

Code: Select all

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
EEIE
0
Output:

Code: Select all

1,2 4,2
2,1 2,4
Not found
Not found
Hope it helps. :)
Ami ekhono shopno dekhi...
HomePage

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Sun Mar 05, 2006 7:57 am

I know I am re-asking a question from another post, but no one replied to that one. What are the valid ways a word can appear in the puzzle? Right now I am checking right, down, right-down, left, left-down, left-up. Should I check for the remaining 2 directions (ie up, right-up)? Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Mar 05, 2006 7:50 pm

I am checking right, down, left, right-down, left-down, left-up, right-up.

Hope it works.
Last edited by Jan on Fri Apr 21, 2006 8:03 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

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

Post by Darko » Fri Apr 21, 2006 7:37 pm

I am guessing that test data is not that great because I got AC with both 5 and 7 directions.

But I am not sure where you got 5 from, Jan? (I was doing something silly, so I tried 5 thinking that was the reason for my WA)

Statement excludes only one direction from what I understand:
A word is ``found'' if all the characters in the word can be traced in a single (unidirectional) horizontal, vertical, or diagonal line in the letter matrix. Words may not ``wrap around'' rows or columns, but horizontal and diagonal words may proceed from right to left (``backwards'').
Darko

[EDIT] Well, I tried with 8 and it worked, I don't think that there was intention to exclude any directions, it was just worded poorly.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Apr 21, 2006 8:01 pm

Thanks Darko for pointing the error. :oops: Sorry about that. Actually I solved it a long time ago. And when I checked my code I missed 2 parts.

In my code I m checking 7 directions. But its quite amaizing that you got Accepted with 5 directions.

Thank u again.
Ami ekhono shopno dekhi...
HomePage

Hiroshi Saito
New poster
Posts: 1
Joined: Sat May 12, 2007 3:50 pm

Post by Hiroshi Saito » Sat May 12, 2007 4:11 pm

I think the last case would be 4,4 1,1.
Jan wrote:I solved it long time ago. So I have forgot the restrictions. But you can try the input output set. Your code returns wrong answer for the set.

Input:

Code: Select all

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
EEIE
0
Output:

Code: Select all

1,2 4,2
2,1 2,4
Not found
Not found
Hope it helps. :)

Here is my input/output. This may help you.

Input:

Code: Select all

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
EKE
KSID
CSID
EIEEE
EEEIE
EKECE
ECEKE
I
0
Output

Code: Select all

1,2 4,2
2,1 2,4
Not found
1,3 3,5
2,4 2,1
Not found
1,1 5,5
5,5 1,1
1,5 5,1
5,1 1,5
2,2 2,2

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

Re: 422 word search wonder

Post by kier.guevara » Tue Feb 12, 2013 5:08 pm

Code: Select all

ACCEPTED
can you guys put more I/O? I don't know whats wrong with my code
Last edited by kier.guevara on Wed Feb 13, 2013 10:11 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 422 word search wonder

Post by brianfry713 » Tue Feb 12, 2013 10:25 pm

Input:

Code: Select all

5
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
ABC
GMS
HMR
NRV
IHGF
OIC
UPKFA
VRNJ
ASDF
0
Correct output:

Code: Select all

1,1 1,3
2,2 4,4
2,3 4,3
3,4 5,2
2,4 2,1
3,5 1,3
5,1 1,1
5,2 2,5
Not found
Check input and AC output for thousands of problems on uDebug!

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

Re: 422 word search wonder

Post by kier.guevara » Wed Feb 13, 2013 10:10 am

Thanks brianfry! I got AC!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re:

Post by mgavin2 » Wed Jul 23, 2014 7:49 pm

Hiroshi Saito wrote:
Here is my input/output. This may help you.

Input:

Code: Select all

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
EKE
KSID
CSID
EIEEE
EEEIE
EKECE
ECEKE
I
0
Output

Code: Select all

1,2 4,2
2,1 2,4
Not found
1,3 3,5
2,4 2,1
Not found
1,1 5,5
5,5 1,1
1,5 5,1
5,1 1,5
2,2 2,2
I'm so confused how that output would be AC. Shouldn't CISD be found within the letters? I get brianfry's input/output just fine... but I still get WA on this problem. Does anyone have anymore tricky test cases?
all that matters is AC

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

Re: 422 word search wonder

Post by Darko » Wed Jul 23, 2014 8:37 pm

It is as simple as checking all possible starting positions and checking all 8 directions.

Something is wrong with your implementation.

How about this one:

Code: Select all

2
AA
AA
AAA
0

Post Reply

Return to “Volume 4 (400-499)”