422 - Word-Search Wonder
Moderator: Board moderators
422
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]
[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]
-
- New poster
- Posts: 3
- Joined: Sun Oct 05, 2003 1:32 pm
- Location: Campinas-SP
- Contact:
422 ???????????????????????????????????????????? 422
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)
"Hay que endurecer, pero sin perder la ternura jamas!"(Che Guevara)
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh
422 - Word-Search Wonder
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]

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");
}
}
}
Jalal : AIUB SPARKS
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:
Output:
Hope it helps. 
Input:
Code: Select all
5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
EEIE
0
Code: Select all
1,2 4,2
2,1 2,4
Not found
Not found

Ami ekhono shopno dekhi...
HomePage
HomePage
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:
[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.
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:
DarkoA 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'').
[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.
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.

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
HomePage
-
- New poster
- Posts: 1
- Joined: Sat May 12, 2007 3:50 pm
I think the last case would be 4,4 1,1.
Here is my input/output. This may help you.
Input:
Output
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:Output:Code: Select all
5 EDEEE DISKE ESEEE ECEEE EEEEE DISC DISK DISP EEIE 0
Hope it helps.Code: Select all
1,2 4,2 2,1 2,4 Not found Not found
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
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
-
- New poster
- Posts: 30
- Joined: Thu Jul 19, 2012 11:24 pm
Re: 422 word search wonder
Code: Select all
ACCEPTED
Last edited by kier.guevara on Wed Feb 13, 2013 10:11 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 422 word search wonder
Input:Correct output:
Code: Select all
5
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
ABC
GMS
HMR
NRV
IHGF
OIC
UPKFA
VRNJ
ASDF
0
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!
-
- New poster
- Posts: 30
- Joined: Thu Jul 19, 2012 11:24 pm
Re: 422 word search wonder
Thanks brianfry! I got AC!
Re:
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?Hiroshi Saito wrote:
Here is my input/output. This may help you.
Input:OutputCode: Select all
5 EDEEE DISKE ESEEE ECEEE EEEEE DISC DISK DISP EKE KSID CSID EIEEE EEEIE EKECE ECEKE I 0
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
all that matters is AC
Re: 422 word search wonder
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:
Something is wrong with your implementation.
How about this one:
Code: Select all
2
AA
AA
AAA
0