## 422 - Word-Search Wonder

Moderator: Board moderators

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

### 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,s;
scanf("%d",&n);
for(x=0;x<n;x++)
scanf("%s",data[x]);
while(1)
{
scanf("%s",s);
if(s=='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)
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
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

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)

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### 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: 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,int size)
{
int i,j,k,flage=0,len=strlen(string);
int count_d,count_h,count_v;
char inverse;

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)
{
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==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)
{
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)
{
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==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;
//	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
}
}
}
``````
[/code]
Jalal : AIUB SPARKS

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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
Hope it helps. Ami ekhono shopno dekhi...
HomePage

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
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
Contact:
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
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
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

Hiroshi Saito
New poster
Posts: 1
Joined: Sat May 12, 2007 3:50 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
Hope it helps. 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
1,3 3,5
2,4 2,1
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

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

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

Thanks brianfry! I got AC!

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

### Re:

Hiroshi Saito wrote:

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
1,3 3,5
2,4 2,1
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

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

``````2