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.

I can't understand the word.
What does it mean?
Thanks.

Don't understand where is problem? Help me please someone!
Here my code...

{$Apptype console}

const
 dx : array [1..4]of longint = (1 , -1 , 0 , 0);
 dy : array [1..4]of longint = (0 , 0 , -1 , 1);


var
 a : array [0..5 , 0..5] of char;
 was : array [0..5,0..5] of boolean;
 i , j : longint;
 s : string;
 n : longint;

Function Same(rem : longint; x , y : longint) : boolean;
var i : longint;
    ok : boolean;
 begin
   if rem = n + 1 then Same := true else

    if was[x, y] then Same := false else

     begin

      ok := false;
      was[x , y] := true;

      if a[x , y] = s[rem] then
        for i := 1 to 4 do
         if Same(rem + 1, x + dx[i] , y + dy[i]) then ok := true;

      Same := ok;
      was[x , y] := false;
     end;
 end;

 Function check(s : string) : boolean;
 var ch  : boolean;
  begin
   ch := false;

   while s[1] = ' ' do delete(s , 1 , 1);
   while s[length(s)] = ' ' do delete(s , 1 , 1);

   n := length(s);
    for i:= 1 to 4 do
     for j:= 1 to 4 do
      if same(1 , i, j) then ch := true;

    check := ch;
  end;

Begin

 for i:= 0 to 5 do
  for j:= 0 to 5 do
   a[i, j] := '1';

 fillchar(was , sizeof(was) , false);


 for i:= 1 to 4 do
  begin

    for j:= 1 to 4 do
     read(a[i , j]);

    readln;
  end;


 readln(n);

  for i:= 1 to n do
   begin
    readln(s);
    if check(s)  then writeln(s,': YES') else writeln(s,': NO');
   end;


end.

thanks... I got AC!

Edited by author 12.03.2008 04:00

Please explain me where is tricky?
If you don't want say tricky, give some tests.
I use backtracking.

Edited by author 06.03.2008 16:22

Edited by author 06.03.2008 16:23

Can we start the walk at any position of the puzzle? Or must start from the upper left corner?