10010 - Where's Waldorf?
Moderator: Board moderators
10010 - Where's Waldorf?
Is there something wrong with the judge? This is the second problem in a week that has been spit back Invalid Memory Reference which I can only assume is an out of bounds problem, but I've scoured my code and I can't seem to find anywhere where this is even possible, and EVERYTHING I try when i run the program works beautifully. Here is my code, granted I could probably have written a compact and more efficient program, but I just wrote this out quickly using cut and paste without thinking about it too much. If anybody can point out where an out of bounds or invalid memory reference could possibly happen, please let me know because I am stumped.
[cpp]
#include <iostream>
#include <vector>
#include<string>
using namespace std;
void findit(vector< vector<char> > &grid, string s)
{
int z;
for (int y=0; y<grid.size(); y++)
{
for (int x=0; x<grid[0].size(); x++)
{
if (grid[y][x]!=s[0])
continue;
// forward
if (x<=grid[0].size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// backward
if (x>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// down
if (y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// up
if (y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal down to right
if (x<=grid[0].size()-s.length() && y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal down to left
if (x>=s.length()-1 && y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal up to left
if (x>=s.length()-1 && y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal up to right
if (x<=grid[0].size()-s.length() && y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
}
}
}
void allLower(string &s)
{
for (int x=0; x<s.length(); x++)
s[x]=tolower(s[x]);
}
int main()
{
vector<int> vec(8,0)
cout<<vec[10];
int x,y,z;
string buff;
int cases;
cin>>cases;
getline(cin,buff);
cin.ignore(255,'\n');
for (x=0; x<cases; x++)
{
int height, width;
cin>>height>>width;
vector<char> vec;
vector< vector<char> > grid;
for (y=0; y<height; y++)
{
vec.clear();
for (z=0; z<width; z++)
{
char c;
cin>>c;
vec.push_back(tolower(c));
}
grid.push_back(vec);
}
int num;
cin>>num;
for (y=0; y<num; y++)
{
string word;
cin>>word;
allLower(word);
findit(grid,word);
}
if (x!=cases-1)
{
cout<<endl;
getline(cin,buff);
cin.ignore(255,'\n');
}
}
return 0;
}
[/cpp]
[cpp]
#include <iostream>
#include <vector>
#include<string>
using namespace std;
void findit(vector< vector<char> > &grid, string s)
{
int z;
for (int y=0; y<grid.size(); y++)
{
for (int x=0; x<grid[0].size(); x++)
{
if (grid[y][x]!=s[0])
continue;
// forward
if (x<=grid[0].size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// backward
if (x>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// down
if (y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// up
if (y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal down to right
if (x<=grid[0].size()-s.length() && y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal down to left
if (x>=s.length()-1 && y<=grid.size()-s.length())
{
for (z=0; z<s.length(); z++)
{
if (grid[y+z][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal up to left
if (x>=s.length()-1 && y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x-z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
// diagonal up to right
if (x<=grid[0].size()-s.length() && y>=s.length()-1)
{
for (z=0; z<s.length(); z++)
{
if (grid[y-z][x+z]!=s[z])
break;
if (z==s.length()-1)
{
cout<<y+1<<" "<<x+1<<endl; return;
}
}
}
}
}
}
void allLower(string &s)
{
for (int x=0; x<s.length(); x++)
s[x]=tolower(s[x]);
}
int main()
{
vector<int> vec(8,0)
cout<<vec[10];
int x,y,z;
string buff;
int cases;
cin>>cases;
getline(cin,buff);
cin.ignore(255,'\n');
for (x=0; x<cases; x++)
{
int height, width;
cin>>height>>width;
vector<char> vec;
vector< vector<char> > grid;
for (y=0; y<height; y++)
{
vec.clear();
for (z=0; z<width; z++)
{
char c;
cin>>c;
vec.push_back(tolower(c));
}
grid.push_back(vec);
}
int num;
cin>>num;
for (y=0; y<num; y++)
{
string word;
cin>>word;
allLower(word);
findit(grid,word);
}
if (x!=cases-1)
{
cout<<endl;
getline(cin,buff);
cin.ignore(255,'\n');
}
}
return 0;
}
[/cpp]
10010 - Waldorf! Where is it?
Hy!
I really do not know why I get WA. Here is my code:
I would appreciate some sample input and output!
Thanks
I really do not know why I get WA. Here is my code:
Code: Select all
/*
* autor: Lamasanu Ion, Iulie 2004
* ACM Contest training
* Where is Waldorf? 10010
*/
#include <stdio.h>
#include <ctype.h>
char grid[100][100];
char word[2600];
char vizited[100][100];
int m, n; /*** nr de linii, resp. coloane */
int gasit(int x, int y, char word[]);
void init(void);
int main(void)
{
int t, i, j, k;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &m, &n);
for(i=0; i<m; i++)
{
scanf("%s", &grid[i]);
for(j=0; grid[i][j]; j++)
grid[i][j] = toupper(grid[i][j]);
}
scanf("%d", &k);
for(i=0; i<k; i++)
{
int x, y;
scanf("%s", word);
for(j=0; word[j]; j++)
word[j] = toupper(word[j]);
init(); /**** */
x=0;
while(x<m)
{
y=0;
while(y<n)
{
if( gasit(x,y,word) )
{
printf("%d %d\n", x+1, y+1);
x=m; y=n;
}
y++;
}
x++;
}
}
puts("");
}
return 0;
}
int dx[] = {0,1,1,1,0,-1,-1,-1},
dy[] = {-1,-1,0,1,1,1,0,-1};
int gasit(int x, int y, char word[])
{
vizited[x][y]++;
if( grid[x][y] == *word )
{
int i, a, b, flag=0;
if( *(word+1) == 0 )
return 1;
for(i=0; i<8; i++)
{
a = x+dx[i];
b = y+dy[i];
if(0<=a && a<m && 0<=b && b<n && vizited[a][b]==0)
{
flag = gasit(a,b,word+1);
if( flag )
break;
}
}
return flag;
}
vizited[x][y]--;
return 0;
}
void init(void)
{
int i, j;
for(i=0; i<100; i++)
for(j=0; j<100; j++)
vizited[i][j] = 0;
}
Thanks
Things are simple, but we make them complex.
thanks
thanks wolf.
I will revise the source code. Thank you for answering.
I will revise the source code. Thank you for answering.
Things are simple, but we make them complex.
10010 Where the hell is Waldorf? I can't find it!!!
Hye... I am very disappointed. I submitted this problem 20 times and I've got WA for all. Is there some treaky inputs?
Please, people, help me with this easy problem.
Look a little at my code:
Please, people, help me with this easy problem.
Look a little at my code:
Code: Select all
#include <stdio.h>
#include <ctype.h>
int m, n; /* num of line & columns */
char grid[60][60];
char viz[60][60]; /* vizited letters */
void init_viz(void);
int search(char word[], int a, int b); /* srch the word */
int main(void)
{
int tst, i, j, k, found;
char word[3000];
scanf("%d", & tst);
while(tst--)
{
scanf("%d%d", &m, &n);
for(i = 0; i < m; i++)
{
scanf("%s", grid[i]);
for(j = 0; j < n; j++)
grid[i][j] = toupper(grid[i][j]);
}
scanf("%d", &k);
while(k--)
{
scanf("%s", word);
for(i = 0; word[i]; i++)
word[i] = toupper(word[i]);
/* srch in the grid[][] */
found = 0;
init_viz();
for(i = 0; i < m && !found; i++)
for(j= 0; j < n && !found; j++)
if(word[0] == grid[i][j])
if(search(word, i, j) == 1)
{
printf("%d %d\n", i+1, j+1);
found = 1;
}
}
if(tst > 0)
puts("");
}
return 0;
}
void init_viz(void)
{
int i, j;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
viz[i][j] = 0;
}
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {-1,-1,0,1,1,1,0,-1};
int search(char word[], int a, int b)
{
viz[a][b] = 1;
if( *(word+1) == '\0' )
return 1;
else
{
int i, nx, ny;
for(i = 0; i < 8; i++)
{
nx = a + dx[i];
ny = b + dy[i];
if(0 <= nx && nx < m && 0 <= ny && ny < n
&& !viz[nx][ny] && *(word+1)==grid[nx][ny] )
if( search(word+1, nx, ny) == 1)
return 1;
}
}
viz[a][b] = 0;
return 0;
}
Things are simple, but we make them complex.
10010
I'm getting a little frustrated with Where's Waldorf. I can't find a problem by reviewing my code, and the sample data in the problem works fine. But I keep getting WA.
Here's the sample data I'm using; as you can see, I'm going for edge cases.
and here's my output
Does anyone have any more challenging sample data?
Here's the sample data I'm using; as you can see, I'm going for edge cases.
Code: Select all
1
8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
7
fha
fro
ggi
Waldorf
Bambi
Betty
Dagbert
Code: Select all
3 1
8 11
1 11
2 5
2 3
1 2
7 8
Yes, for that input your program goes well.. but, you should be prove for that input
and the output is :
![:wink:](./images/smilies/icon_wink.gif)
![:wink:](./images/smilies/icon_wink.gif)
Code: Select all
2
8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
7
fha
fro
ggi
Waldorf
Bambi
Betty
Dagbert
6 8
dbFdxHYo
IaVNewTd
aDvEntuR
YoYoYoYo
McIeNOto
BiDorKWa
6
yo
cieno
dia
adventur
yoyo
dork
Code: Select all
3 1
8 11
1 11
2 5
2 3
1 2
7 8
1 7
5 2
1 1
3 1
4 1
6 3
![:wink:](./images/smilies/icon_wink.gif)
Thanks. Here's the output I get from your sample set:
It is correct, isn't it? The problem description says "the output of two consecutive cases must be separated by a blank line". But your listing didn't do that.
.B ekiM
Code: Select all
C:\projects\WheresWaldorf\Debug>WheresWaldorf.exe < more_input.txt
3 1
8 11
1 11
2 5
2 3
1 2
7 8
1 7
5 2
1 1
3 1
4 1
6 3
.B ekiM
10010 Where's Waldorf TLE :( help!!!
Hi when I saw this problem I thought it would be an easy one ( and probably it is) but I tried to solve it just using brute force but it seams it doesn't work :S, or maybe I'm screwing somithing up ...
If someone can help me with my code, or a litle clue or in/outs it would be a great help. Any help of any kind is welcome![:)](./images/smilies/icon_smile.gif)
Thanks a lot, and please help me !!![:P](./images/smilies/icon_razz.gif)
If someone can help me with my code, or a litle clue or in/outs it would be a great help. Any help of any kind is welcome
![:)](./images/smilies/icon_smile.gif)
Thanks a lot, and please help me !!
![:P](./images/smilies/icon_razz.gif)
Code: Select all
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define X 55
char A[X][X];
int N,M,K,x[21],y[21],t,L[21],G[21];
char buffer[21][X];
void check(int s, int xx, int yy,int r, int c){
int i,j,pasos=0;
for (i=xx,j=yy;i<N && i>=0 && j<M && j>=0;i+=r,j+=c){
if (A[i][j] != buffer[s][pasos++])
return ;
if (pasos == L[s])break;
}
if (pasos != L[s])return;
t = 1;
}
void donde(){
int i,j,k;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
for(k=0;k<K;k++){
t = 0;
if (A[i][j] == buffer[k][0] && !G[k]){
check(k,i,j,-1,0);
check(k,i,j,1,0);
check(k,i,j,1,1);
check(k,i,j,-1,1);
check(k,i,j,-1,-1);
check(k,i,j,1,-1);
check(k,i,j,0,-1);
check(k,i,j,0,1);
if (t){
G[k] = 1;
x[k] =i+1; y[k] =j+1;
}
}
}
}
void tol(){
int i,j;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
A[i][j] = tolower(A[i][j]);
for(j=0;j<K;j++)
for(i=0;i<L[j];i++)
buffer[j][i] = tolower(buffer[j][i]);
}
void limpia(){
int i;
for(i=0;i<K;i++)
G[i] = 0;
}
int main(){
int T,i,j;
FILE *e = stdin;
fscanf(e,"%d",&T);
for(j=0;j<T;j++){
fscanf(e,"%d %d",&N,&M);
for(j=0;j<N;j++)
fscanf(e,"%s",&A[j]);
fscanf(e,"%d",&K);
for(j=0;j<K;j++){
fscanf(e,"%s",&buffer[j]);
L[j] = strlen(buffer[j]);
}
tol();
donde();
for(j=0;j<K;j++)
printf("%d %d\n",x[j],y[j]);
limpia();
}
return 0;
}
I catch my error :$
Hi I just found my error hehehe I was using the same variable for two different cicles... and got ACC.
:$ Ooops ...
:$ Ooops ...
-
- Learning poster
- Posts: 70
- Joined: Sat Feb 05, 2005 9:38 am
- Location: Gurukul
10010 Where's Waldrof?
Hi all,
I'm getting WA. Please give some I/O. Thanx in advance.
I'm getting WA. Please give some I/O. Thanx in advance.
Some Love Stories Live Forever ....
WA
Hi,
Im also face WA for this problem. Plz help me to find out error. Here is my code. My code is clumshy enough. The code should be small. But i just want to know what i'm missing. Thanx in advance.
Im also face WA for this problem. Plz help me to find out error. Here is my code. My code is clumshy enough. The code should be small. But i just want to know what i'm missing. Thanx in advance.
Code: Select all
Cut after Acc...
Last edited by Chok on Tue Jul 19, 2005 7:00 pm, edited 2 times in total.