11283 - Playing Boggle

[Scarecrow]

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

[brianfry713]

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.

[shiam]

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

[uDebug]

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

[Mukit Chowdhury]

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