Page 1 of 2

422

Posted: Tue Jul 23, 2002 1:48 pm
by htl
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]

Posted: Tue Jul 23, 2002 5:32 pm
by htl
Uh...I made an embarrassing mistake... I replaced the '3' with 'n-1' and got accepted.

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

Posted: Sat Jul 31, 2004 4:12 pm
by Thiago Serra
In which directions should I consider to get ACC?

422 - Word-Search Wonder

Posted: Mon Jan 17, 2005 6:01 pm
by CodeMaker
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]

Posted: Thu Sep 15, 2005 10:57 pm
by Jan
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. :)

Posted: Sun Mar 05, 2006 7:57 am
by stcheung
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.

Posted: Sun Mar 05, 2006 7:50 pm
by Jan
I am checking right, down, left, right-down, left-down, left-up, right-up.

Hope it works.

Posted: Fri Apr 21, 2006 7:37 pm
by Darko
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.

Posted: Fri Apr 21, 2006 8:01 pm
by Jan
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.

Posted: Sat May 12, 2007 4:11 pm
by Hiroshi Saito
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

Re: 422 word search wonder

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

Code: Select all

ACCEPTED
can you guys put more I/O? I don't know whats wrong with my code

Re: 422 word search wonder

Posted: Tue Feb 12, 2013 10:25 pm
by brianfry713
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

Re: 422 word search wonder

Posted: Wed Feb 13, 2013 10:10 am
by kier.guevara
Thanks brianfry! I got AC!

Re:

Posted: Wed Jul 23, 2014 7:49 pm
by mgavin2
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?

Re: 422 word search wonder

Posted: Wed Jul 23, 2014 8:37 pm
by Darko
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