422 - Word-Search Wonder

[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]

[htl]

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

[Thiago Serra]

In which directions should I consider to get ACC?

[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

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]

[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.

[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.

[Jan]

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

Hope it works.

[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.

[Jan]

Thanks Darko for pointing the error. 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.

[Hiroshi Saito]

I think the last case would be 4,4 1,1.

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]

Code: Select all

ACCEPTED

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

[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

[kier.guevara]

Thanks brianfry! I got AC!

[mgavin2]

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?

[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