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 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.
11283 - Playing Boggle
Moderator: Board moderators
Re: 11283 - Playing Boggle
Do or do not. There is no try.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11283 - Playing Boggle
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!
Re: 11283 - Playing Boggle
this code takes more than 5 sec for the case below:
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 <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 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;
}
Re: 11283 - Playing Boggle
Here's a test case that helped me during testing / debugging.
Input:
AC Output:
Input:
Code: Select all
1
KCKP
ADKP
BCDD
KXKX
1
KKKK
Code: Select all
Score for Boggle game #1: 0
-
- Learning poster
- Posts: 99
- Joined: Fri Aug 17, 2012 9:23 pm
- Location: Dhaka
- Contact:
Re: 11283 - Playing Boggle
@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.