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:

Code: Select all

Removed after AC

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

Code: Select all

1
KKKK
ADKK
BCKK
KKKK

1
ABCDA

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

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.

Code: Select all

Removed after AC


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

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:

Code: Select all

Score for Boggle game #1: 44

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

Code: Select all

AC

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