Page 1 of 2
11283 - Playing Boggle
Posted: Mon Sep 29, 2008 5:21 am
by slxst
I'm getting WA.
A low "Total Submissions / Solving %" with a high "Total Users / Solving %" usually means a tricky input.
The problem says "A blank line always precedes the letter grid" It seems like a clue but I can't figure it out.
Thanks!
My code:
Re: 11283 - Playing Boggle
Posted: Mon Sep 29, 2008 6:49 am
by 898989
Hi, I have tried it now. I also got WA.
our codes is same way, but i think u have another bug.
When u START searching from i, j, you do not mark this position as visited, so it may be used again
If i am right, then your code will fail in this case
Re: 11283 - Playing Boggle
Posted: Mon Sep 29, 2008 4:10 pm
by 898989
Hi again;
I got AC, after figuring out my stupid typo.
In ur code, no problems except the case I mentioned above. This case answer should be ZERO.
Otherwise, the problem is direct in its input & output.
GoodLuck
Re: 11283 - Playing Boggle
Posted: Mon Sep 29, 2008 8:35 pm
by slxst
Thanks 898989!
That was the mistake! (I can't believe how did I miss it) I finally got AC
Re: 11283 - Playing Boggle
Posted: Fri Jan 23, 2009 10:11 pm
by tanmoy
i use dfs but getting tle plz help
Code: Select all
#include<stdio.h>
#include<string.h>
#include<memory.h>
#define MAX 100
char GAME[4][4];
bool MAP[4][4];
char c[134];
int reach[8][2]={{+0,+1},{+0,-1},{-1,+0},{-1,+1},{-1,-1},{+1,-1},{+1,+0},{+1,+1}},R,C,l,count=0;
void dfs(int i,int j,int depth){
if(GAME[i][j]!=c[depth])return ;
if(depth==(l-1)){
if(l==3)count++;
else if(l==4)count++;
else if(l==5)count+=2;
else if(l==6)count+=3;
else if(l==7)count+=5;
else count+=11;
return;
}
MAP[i][j]=false;
for(int k=0;k<8;k++){
if(i+reach[k][0]<0||i+reach[k][0]>=4||j+reach[k][1]<0||j+reach[k][1]>=4)continue;
if(MAP[i+reach[k][0]][j+reach[k][1]])dfs(i+reach[k][0],j+reach[k][1],depth+1);
}
MAP[i][j]=true;
}
int main(){
int i,q,n,m,w,x=0;
char ch[6];
gets(ch);
sscanf(ch,"%d",&w);
printf("\n");
for(q=0;q<w;q++){
memset(MAP,true,sizeof(MAP));
if(q)printf("\n");
count=0;
for(i=0;i<4;i++)
gets(GAME[i]);
gets(ch);
sscanf(ch,"%d",&n);
for(m=0;m<n;m++){
gets(c);
l=strlen(c);
for(i=0;i<4;i++)
for(int j=0;j<4;j++)
if(c[0]==GAME[i][j]){R=i;C=j;break;}
dfs(R,C,0);
}
x++;
printf("Score for Boggle game #%d: %d\n",x,count);
}
return 0;
}
Re: 11283 - Playing Boggle
Posted: Tue Feb 24, 2009 12:04 pm
by SePulTribe
This is my code. It seems so correct, but it keeps getting WA no matter the fact that I've tried many test cases and checked with different sites. Please help.
Re: 11283 - Playing Boggle
Posted: Fri Feb 27, 2009 12:37 pm
by Jan
Try the cases.
Input:
Code: Select all
3
TNXO
AAEI
IOSR
BFRH
8
OATS
TAXES
RISE
ANNEX
BOAT
FROSH
HAT
TRASH
FNEI
OBCN
EERI
VSIR
1
BEER
ABCD
HGFE
IJKL
PONM
20
ABCDEFGHIJKLMNOP
ABCDEFGHIJKLMNO
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKL
ABCDEFGHIJK
ABCDEFGHIJ
ABCDEFGHI
ABCDEFGH
ABCDEFG
ABCDEF
ABCDE
ABCD
ABC
AHIPOJGBCFKNMLED
MNOPIJKLEFGHDCBA
MLEDCFKNOJGBAHIP
GBCDEFKLMNOJIHA
DCBAHGFELKJIPONM
PIHABGJONKFCDELM
Code: Select all
Score for Boggle game #1: 6
Score for Boggle game #2: 1
Score for Boggle game #3: 166
Re: 11283 - Playing Boggle
Posted: Fri Feb 27, 2009 3:15 pm
by SePulTribe
Thanks man. I got an AC. Turns out my mistake was to count the score in the DFS. Even with a flag to supposedly prevent the counting of the score more than once for a word, the judge's test cases still managed to make it fail.
Re: 11283 - Playing Boggle
Posted: Fri Jun 26, 2009 9:59 pm
by sujon
Anybody please help me . This simple code give me WA.
Code: Select all
///// dfs algorithom
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
//typedef __int64 longlong;
//typedef long long longlong;
int m,n,visit[100][100],l;
char g[100][100],word[100];
int found;
void init()
{
int i,j;
for(i=0;i<=5;i++)
for(j=0;j<=5;j++)
visit[i][j]=0;
}
void dfs(int x,int y,int pos)
{
if(pos==l-1)
{
found=1;
return ;
}
visit[x][y]=1;
int i,j;
for(i=x-1;i<=x+1;i++)
for(j=y-1;j<=y+1;j++)
if(i>=0&&i<4&&j>=0&&j<4)
if( pos+1<l&&g[i][j]==word[pos+1]&&!visit[i][j])
dfs(i,j,pos+1);
}
int main()
{
int i,j,set,c=0,sum;
char temp[100];
int score[20];
score[3]=1;
score[4]=1;
score[5]=2;
score[6]=3;
score[7]=5;
for(i=8;i<20;i++)
score[i]=11;
// freopen("sujon.txt","r",stdin);
// freopen("sujon2.txt","w",stdout);
gets(temp);
sscanf(temp,"%d",&set);
while(set--)
{
gets(temp);// for blank
init();
for(i=0;i<4;i++)
gets(g[i]);
gets(temp);
sscanf(temp,"%d",&n);
sum=0;
while(n--)
{
gets(word);
l=strlen(word);
found=0;
for(i=0;i<4&&!found;i++)
for(j=0;j<4;j++)
if(g[i][j]==word[0]&&!visit[i][j])
{
dfs(i,j,0);
if(found)
sum+=score[l];
init();
if(found)
break;
}
}
printf("Score for Boggle game #%d: %d\n",++c,sum);
}
return 0;
}
Re: 11283 - Playing Boggle
Posted: Thu Sep 09, 2010 3:28 pm
by Shafaet_du
I have solved it after lots of effort. Here are some I/O from my ac code:
Code: Select all
2
SEVO
GOOO
BITL
OBXN
5
LOOOO
GOO
LOOV
BITLOOT
OIOO
AABB
CCDD
QQEE
DDFF
5
FEDBDBCACA
FEDBDECCAQDQD
FEDDEFF
DQCAABBDEF
CDQE
output
Code: Select all
Score for Boggle game #1: 5
Score for Boggle game #2: 23
Re: 11283 - Playing Boggle
Posted: Fri Jun 17, 2011 1:17 am
by shamsacm
Try this
Input:
Code: Select all
1
aaaa
aaaa
aaaa
aaab
5
aaaaaaaaaaaaaaab
baaaaaaaaaaaaaaa
aaaaaaabaaaaaaaa
aaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaa
Output:
Re: 11283 - Playing Boggle
Posted: Tue Aug 16, 2011 7:44 pm
by Imti
I was really tired of this problem..was getting WA repeatedly...Let me show what was giving me WA:
I was taking Input Like Below:
Code: Select all
scanf("%d",&kase);
getchar();
while(kase--)
{
getchar();
for(i=0;i<4;i++)
gets(grid[i]);
scanf("%d",&n);
getchar();
while(n--)
{
gets(word);
//rest of the code here
}
}
And above process was giving me WA..But when I changed this to:
Code: Select all
gets(word);
sscanf(word,"%d",&kase);
while(kase--)
{
getchar();
for(i=0;i<4;i++)
gets(grid[i]);
gets(word);
sscanf(word,"%d",&n);
while(n--)
{
gets(word);
}
And this gave me acc..
what was wrong with first method??
Re: 11283 - Playing Boggle
Posted: Wed Apr 18, 2012 8:04 pm
by Scarecrow
can some1 plz find out the bug in my code? it's keeping me getting WA continuously
plz help some1
Re: 11283 - Playing Boggle
Posted: Thu Apr 19, 2012 12:05 am
by brianfry713
I did some slight modifications to your code and got AC. Instead of using getchar() and counting on that being a newline, try using while(getchar()!='\n');
That way your code will work if there are trailing whitespaces or DOS style newlines.
Re: 11283 - Playing Boggle
Posted: Thu Apr 19, 2012 12:18 am
by Scarecrow
AC