If you use mask as two-dimensional array you probably will get TLE, instead of this use bitset from STL

Edited by author 20.09.2021 15:25

Though without Aho-Corasick and without trie and without any optimizations simply DFS with used [i] [j]  and backtracking is fast

i ended up counting all possible Strings can be composed quickly.

so preprocessing gives me

552 of the 16 symbols words
27956 of less than 16 symbols words (including those who are 1)

try this test
wydh
smdb
dmks
piwo
3
dhbdmy
wsmydd
dhbdmy

ans:

dhbdmy: YES
wsmydd: YES
dhbdmy: YES

I'm using simple DFS from every point and got TLE on 5th test. Wich algo should I use to solve it faster?

Sorry for double-posting...

Edited by author 25.08.2012 23:33

I have WA #6. For all my tests program works correctly. Can you give me some tests?

Do not rape your brain with this problem:), since constraints are really small, - just run straight dynamic, it's look similar to dfs.
After I've corrected some stupid mistakes I've got AC 0.375 124 КБ, without any optimization

To all of you who cannot overcome #3 !!!

All the suggestions about redundant '\n' and about that the dictionary may have repeated words have nothing to do with WA #3 (read condition carefully).

If you use any kind of backward tracking, be it recursion or DFS, check the "no luck" condition attentively. First i used checking the next letter to be '\0' at the beginning of my recursion function, and if so returned 'true'. This is wrong! You must make word-end check BEFORE you make the next step, otherwise you may get "deadlock" "there is no direction to go" though there is no need to go anymore!!!

Test word for the example table
rabadaabracabrac: YES
(starting from [3,1] in C-like indices).

#include <string>
#include <iostream>
#include <stack>
using namespace std;
char a[6][6];
int b[5][5];
int i,j,n,o,q,p,r,m;
stack <int> si,sj;
bool t=false;
string s;
//******************************************
void inp(){
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
{
cin>>a[i][j];
}
for(m=0;m<5;m++)
{a[m][0]=a[0][m]='-1';
a[m][5]=a[5][m]='-1';
}
}
//******************************************
void copy(){
for(o=1;o<=4;o++)
for(q=1;q<=4;q++)
b[o][q]=1;
}
//******************************************
bool check(string buf){
copy();
for(i=1;i<=4;i++){
for(j=1;j<=4;j++){
if(a[i][j]==buf[p]&&b[i][j]==1)
{p=0;
t=true;
si.push(i);
sj.push(j);
p++;
if(p>=buf.length()) return true;
b[i][j]=0;
}
while(!si.empty()){
/*1*/ if(a[si.top()][sj.top()+1]==buf[p]&&b[si.top()][sj.top()+1]==1){
si.push(si.top());
sj.push(sj.top()+1);
t=true;
p++;
if(p>=buf.length()) return true;
b[si.top()][sj.top()]=0;
}
/*2*/ else if(a[si.top()][sj.top()-1]==buf[p]&&b[si.top()][sj.top()-1]==1){
si.push(si.top());
sj.push(sj.top()-1);
t=true;
p++;
if(p>=buf.length()) return true;
b[si.top()][sj.top()]=0;
}
/*3*/ else if(a[si.top()+1][sj.top()]==buf[p]&&b[si.top()+1][sj.top()]==1){
si.push(si.top()+1);
sj.push(sj.top());
t=true;
p++;
if(p>=buf.length()) return true;
b[si.top()][sj.top()]=0;
}
/*4*/ else
if(a[si.top()-1][sj.top()]==buf[p]&&b[si.top()-1][sj.top()]==1){
si.push(si.top()-1);
sj.push(sj.top());
t=true;
p++;
if(p>=buf.length()) return true;
b[si.top()][sj.top()]=0;
}
if(!t){
si.pop();
sj.pop();
if(p!=0)
p--;
}
t=false;
}//<while();
if(si.empty())
copy();
}
}
return false;
}
//******************************************
int main()
{
inp();
cin>>n;
cin.ignore();
for(r=1;r<=n;r++)
{
cin>>s;
if(check(s)) cout<<s<<": YES"<<endl;
else cout<<s<<": NO"<<endl;
}
system("pause");
return 0;
}

Edited by author 02.03.2009 00:54

Please tell me what is the test 3?

In your example order of words in dictionary is same with order of outputing words, but in the problem's text there is no words about it.
Fix it , please.

I`ve got WA2 some times.
Test

adac
babr
arca
3
abracadabra
ababaab

ababaaba
my programm doing correctly. Where my bag?

I have solved her
My email: victorkr@dsn.ru
please!

i use a standart rec function may be something wrong with input (cin >> s;) may be another. Can you give me 7th test to check this?

First it was:
scanf("%s",&search);

Then:
scanf("%s",&search);
while(search[0]=='\n')
     scanf("%s",&search);

Now I changed it to:
gets(search);
while(search[0]=='\0'||search[0]=='\n')
    gets(search);

None of those work and I know that I'm missing something with the line breaks, but I don't know what.

I used backtracking + hesh table (i firstly generate all possible strings which we can get, and saved them in hesh table). Who knows better solution?

I think that made it right. But my program does not pass the test 3.