11283 - Playing Boggle

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

Code: Select all

Removed after AC

[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

Code: Select all

1
KKKK
ADKK
BCKK
KKKK

1
ABCDA


[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

[slxst]

Thanks 898989!

That was the mistake! (I can't believe how did I miss it) I finally got AC

[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;
}



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

Code: Select all

Removed after AC



[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


Output:

Code: Select all

Score for Boggle game #1: 6
Score for Boggle game #2: 1
Score for Boggle game #3: 166

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

[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;
}



[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


[shamsacm]

Try this

Input:

Code: Select all

1
aaaa
aaaa
aaaa
aaab

5
aaaaaaaaaaaaaaab
baaaaaaaaaaaaaaa
aaaaaaabaaaaaaaa
aaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaa

Output:

Code: Select all

Score for Boggle game #1: 44

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

[Scarecrow]

can some1 plz find out the bug in my code? it's keeping me getting WA continuously plz help some1

Code: Select all

AC


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

[Scarecrow]

AC