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

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

Re: 11283 - Playing Boggle

Post by Scarecrow » Thu Apr 19, 2012 1:23 am

brianfry713 wrote: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.
thnx :D i got AC. but why was the problem occurring ? do they deliberately insert white spaces in the input? can u explain a bit more plz?
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 10:55 pm

They might add extra spaces and on this problem it seems they did. Make your code handle it in case they do. Always read the problem statement carefully.
Check input and AC output for thousands of problems on uDebug!

shiam
New poster
Posts: 8
Joined: Mon Mar 14, 2011 6:44 am

Re: 11283 - Playing Boggle

Post by shiam » Sat Jun 01, 2013 12:10 am

this code takes more than 5 sec for the case below:

Code: Select all

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
 
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
 
char grid[4][4];
 
int solve(int row, int col, string& input, int pos) {
    if (pos == (int)input.size())
        return pos;
 
    int diff[9][2] = { {0,0}, {-1,0}, {0, -1}, {-1, -1}, {1, 0}, {0, 1}, {1, 1}, {-1, 1}, {1, -1} };
 
    rep (i, 9) {
        if (row+diff[i][0] >= 0 && row+diff[i][0] < 4 && col+diff[i][1] >= 0 && col+diff[i][1] < 4 && grid[row+diff[i][0]][col+diff[i][1]] == input[pos]) {
            grid[row+diff[i][0]][col+diff[i][1]] = '-';
            int result = solve(row+diff[i][0], col+diff[i][1], input, pos+1);
            grid[row+diff[i][0]][col+diff[i][1]] = input[pos];
 
            if (result > 0)
                return result;
        }
    }
    return 0;
}
 
int find_word(string& input) {
    int result = 0;
 
    rep (i, 4) {
        rep (j, 4) {
            if (grid[i][j] != input[0])
                continue;
 
            result = solve(i, j, input, 0);
 
            if (result > 0) {
                i = 5;
                break;
            }
        }
    }
 
    return result;
}
 
int main(void) {
    freopen("jan.txt","r",stdin);
    int n, gameNumber = 0, m;
    string input;
 
    cin >> n;
    cin.ignore(100, '\n');
 
    while (n--) {
        gameNumber++;
        getline(cin, input); // empty line before the grid
 
        rep (i, 4) {
            getline(cin, input);
            rep (j,(int)input.size()) {
                grid[i][j] = input[j];
            }
        }
 
        cin >> m;
        cin.ignore(100, '\n');
 
        int result = 0;
 
        while (m--) {
            getline(cin, input);
 
            int found = find_word(input);
 
            if (found == 3 || found == 4) {
                result += 1;
            } else if (found == 5) {
                result += 2;
            } else if (found == 6) {
                result += 3;
            } else if (found == 7) {
                result += 5;
            } else if (found > 7) {
                result += 11;
            }
        }
 
        cout << "Score for Boggle game #" << gameNumber << ": " << result << endl;
    }
 
    return 0;
}

Code: Select all

1

aaaa
aaaa
aaaa
aaab
5
aaaaaaaaaaaaaaab
baaaaaaaaaaaaaaa
aaaaaaabaaaaaaaa
aaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaa
but it is still AC in UVa 2 sec Time limit. can anyone explain why this happened?
but this same code same logic with some different variable gets TLE. whats the problem with the judge. I really don't know.

Code: Select all

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
 
using namespace std;
 
/*** typedef ***/
 
#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define stream istringstream
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define INF (1<<30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define memsp(x) mem(x,MEMSET_INF)
#define memdp(x) mem(x,-1)
#define memca(x) mem(x,0)
#define eps 1e-9
#define pii pair<int,int>
#define pmp make_pair
#define ft first
#define sd second
#define vi vector<int>
#define vpii vector<pii>
#define si set<int>
#define msi map<string , int >
#define mis map<int , string >
typedef long long i64;
typedef unsigned long long ui64;
 
/** function **/
 
#define SDi(x) sf("%d",&x)
#define SDl(x) sf("%lld",&x)
#define SDs(x) sf("%s",x)
#define SD2(x,y) sf("%d%d",&x,&y)
#define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)
#define pf printf
#define sf scanf
 
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
 
int x8[] = { 1, 0,-1, 0,-1, 1,-1, 1};
int y8[] = { 0, 1, 0,-1,-1, 1, 1,-1};
 
char grid[4][4];
char word[18];
bool vis[4][4];
 
bool dfs(int i,int j,int pos){
     if( pos==(int)strlen(word) - 1 )
        return true;
    vis[i][j] = true;
    int u,v;
    rep(x,8){
        u = i+x8[x], v = j+y8[x];
        if(u>=0 and v>=0 and u<4 and v<4 and !vis[u][v] and grid[u][v]==word[pos+1]){
            bool gotit =  dfs(u,v,pos+1);
            if(gotit){
                vis[i][j] = false;
                return true;
            }
        }
    }
    vis[i][j] = false;
    return false;
}
 
bool findans(){
    rep(i,4) rep(j,4){
        if(grid[i][j]==word[0]){
            bool gotit = dfs(i,j,0);
            if(gotit) return true;
        }
    }
    return false;
}
 
int main()
{
#ifndef ONLINE_JUDGE
        READ("jan.txt");
#endif
    int tc,cas=0;
    SDi(tc);getchar();
    while(tc--){
        memca(vis);
        getchar();
        rep(i,4) gets(grid[i]);
        int query;
        SDi(query);getchar();
        int result = 0;
        while(query--){
            gets(word);
            int found  = 0;
            if(findans()) found = strlen(word);
 
            if (found == 3 || found == 4) {
                result += 1;
            } else if (found == 5) {
                result += 2;
            } else if (found == 6) {
                result += 3;
            } else if (found == 7) {
                result += 5;
            } else if (found > 7) {
                result += 11;
            }
        }
        cout << "Score for Boggle game #" << ++cas << ": " << result << endl;
    }
    return 0;
}

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11283 - Playing Boggle

Post by uDebug » Thu Apr 02, 2015 7:22 am

Here's a test case that helped me during testing / debugging.

Input:

Code: Select all

1

KCKP
ADKP
BCDD
KXKX

1
KKKK
AC Output:

Code: Select all

Score for Boggle game #1: 0
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11283 - Playing Boggle

Post by Mukit Chowdhury » Wed Dec 02, 2015 2:53 pm

@shiam, if I don't get wrong, it happened, because, you mixed cout with scanf(). If time limit is strict, usually mixing cout and scanf() gives TLE.

Post Reply

Return to “Volume 112 (11200-11299)”