11283 - Playing Boggle

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

11283 - Playing Boggle

Post by slxst » Mon Sep 29, 2008 5:21 am

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
Last edited by slxst on Mon Sep 29, 2008 8:20 pm, edited 1 time in total.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Re: 11283 - Playing Boggle

Post by 898989 » Mon Sep 29, 2008 6:49 am

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
Sleep enough after death, it is the time to work.
Mostafa Saad

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Re: 11283 - Playing Boggle

Post by 898989 » Mon Sep 29, 2008 4:10 pm

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
Sleep enough after death, it is the time to work.
Mostafa Saad

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Re: 11283 - Playing Boggle

Post by slxst » Mon Sep 29, 2008 8:35 pm

Thanks 898989!

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

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11283 - Playing Boggle

Post by tanmoy » Fri Jan 23, 2009 10:11 pm

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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 11283 - Playing Boggle

Post by SePulTribe » Tue Feb 24, 2009 12:04 pm

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

Last edited by SePulTribe on Fri Feb 27, 2009 3:14 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11283 - Playing Boggle

Post by Jan » Fri Feb 27, 2009 12:37 pm

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
Ami ekhono shopno dekhi...
HomePage

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 11283 - Playing Boggle

Post by SePulTribe » Fri Feb 27, 2009 3:15 pm

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
New poster
Posts: 5
Joined: Thu Aug 28, 2008 4:17 pm

Re: 11283 - Playing Boggle

Post by sujon » Fri Jun 26, 2009 9:59 pm

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11283 - Playing Boggle

Post by Shafaet_du » Thu Sep 09, 2010 3:28 pm

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
New poster
Posts: 6
Joined: Sat May 07, 2011 12:45 pm

Re: 11283 - Playing Boggle

Post by shamsacm » Fri Jun 17, 2011 1:17 am

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
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11283 - Playing Boggle

Post by Imti » Tue Aug 16, 2011 7:44 pm

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
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11283 - Playing Boggle

Post by Scarecrow » Wed Apr 18, 2012 8:04 pm

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

Code: Select all

AC
Last edited by Scarecrow on Thu Apr 19, 2012 1:20 am, edited 1 time in total.
Do or do not. There is no try.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11283 - Playing Boggle

Post by brianfry713 » Thu Apr 19, 2012 12:05 am

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.
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11283 - Playing Boggle

Post by Scarecrow » Thu Apr 19, 2012 12:18 am

AC
Last edited by Scarecrow on Thu Apr 19, 2012 1:24 am, edited 1 time in total.
Do or do not. There is no try.

Post Reply

Return to “Volume 112 (11200-11299)”