sry, in the findWord function all a's are different e.g
a0, a1....a7
and if(!a) is actually if(a0||a1||...||a7)
thnx
piyush
On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover <piyush4u.iit...@gmail.com>wrote:
> for(i = 0; i < n; i++)
> for(j = 0; j < n; j++){
> setColor(i, j) = black;
> if(A[i][j] == str[0]){
> setColor(i, j) = blue;
> a = findWord(A, i, j, str, 1)
> if(!a) setColor(i, j) = black;
> else break;
> }
> }
>
> findWord(A, i, j, str, k){
> if(k == strlen(str))
> return true;
>
> if(A[i-1][j-1] == str[k] && getColor(i-1, j-1) != blue)
> setColor(i-1, j-1) = blue;
> a = findWord(A, i-1, j-1, str, k+1);
>
> if(A[i-1][j] == str[k] && getColor(i-1, j) != blue)
> setColor(i-1, j) = blue;
> a = findWord(A, i-1, j, str, k+1);
>
> if(A[i-1][j+1] == str[k] && getColor(i-1, j+1) != blue)
> setColor(i-1, j+1) = blue;
> a = findWord(A, i-1, j+1, str, k+1);
>
> if(A[i][j-1] == str[k] && getColor(i, j-1) != blue)
> setColor(i, j-1) = blue;
> a = findWord(A, i, j-1, str, k+1);
>
> if(A[i][j+1] == str[k] && getColor(i, j+1) != blue)
> setColor(i, j+1) = blue;
> a = findWord(A, i, j+1, str, k+1);
>
> if(A[i+1][j-1] == str[k] && getColor(i+1, j-1) != blue)
> setColor(i+1, j-1) = blue;
> a = findWord(A, i+1, j-1, str, k+1);
>
> if(A[i+1][j] == str[k] && getColor(i+1, j) != blue)
> setColor(i+1, j) = blue;
> a = findWord(A, i+1, j, str, k+1);
>
> if(A[i+1][j+1] == str[k] && getColor(i+1, j+1) != blue)
> setColor(i+1, j+1) = blue;
> a = findWord(A, i+1, j+1, str, k+1);
>
> if(!a) setColor(i, j) = black;
>
> return a;
> }
>
> This is a pseudo code. I haven't considered the boundary cases to make it
> understandable.
>
>
>
> On Mon, Sep 19, 2011 at 12:21 AM, vikas <vikas.rastogi2...@gmail.com>wrote:
>
>> hmm, nice questions, can we create an efficient DS to query the
>> strings ??
>>
>>
>> tried using trie but memory prints are very large ( O(n^2) )? :-((
>>
>>
>>
>> On Sep 18, 12:59 pm, Anup Ghatage <ghat...@gmail.com> wrote:
>> > For the mentioned scenario, it seems to be the only feasible solution.
>> >
>> > On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana <
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > bagana.bharatku...@gmail.com> wrote:
>> > > @anup : the time complexity will be very high ...
>> O(n*M*M)...n=#characters
>> > > to be checked...M=size of the matrix ...
>> >
>> > > On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage <ghat...@gmail.com>
>> wrote:
>> >
>> > >> As WgpShashank once pointed out.
>> >
>> > >> Search the whole matrix for the first character instances, for each
>> > >> instance, send the array, string and that char's position to a
>> function that
>> > >> will recursively check its direct neighbors for the next character.
>> > >> Exhaustively check like that for each starting characters appearance
>> till
>> > >> you find the string, if any.
>> >
>> > >> On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg <ankurga...@gmail.com
>> >wrote:
>> >
>> > >>> In a matrix of. characters, find an string. String can be in any way
>> (all
>> > >>> 8 neighbours to be considered)
>> > >>> like find Microsoft in below matrix.
>> >
>> > >>> A
>> > >>> C
>> > >>> P
>> > >>> *R
>> > >>> *C*
>> > >>> *X
>> > >>> *S
>> > >>> **O
>> > >>> *P
>> > >>> *C*
>> > >>> V
>> > >>> *O*
>> > >>> V
>> > >>> N
>> > >>> *I*
>> > >>> W
>> > >>> G
>> > >>> *F
>> > >>> **M
>> > >>> *N
>> > >>> Q
>> > >>> A
>> > >>> *T*
>> > >>> I
>> > >>> T
>> >
>> > >>> *Any Ideas How to Solve/Approach this problem ?*
>> >
>> > >>> --
>> > >>> You received this message because you are subscribed to the Google
>> Groups
>> > >>> "Algorithm Geeks" group.
>> > >>> To post to this group, send email to algogeeks@googlegroups.com.
>> > >>> To unsubscribe from this group, send email to
>> > >>> algogeeks+unsubscr...@googlegroups.com.
>> > >>> For more options, visit this group at
>> > >>>http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > >> --
>> > >> Anup Ghatage
>> >
>> > >> --
>> > >> You received this message because you are subscribed to the Google
>> Groups
>> > >> "Algorithm Geeks" group.
>> > >> To post to this group, send email to algogeeks@googlegroups.com.
>> > >> To unsubscribe from this group, send email to
>> > >> algogeeks+unsubscr...@googlegroups.com.
>> > >> For more options, visit this group at
>> > >>http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > > --
>> >
>> > > **Please do not print this e-mail until urgent requirement. Go Green!!
>> > > Save Papers <=> Save Trees
>> > > *BharatKumar Bagana*
>> > > **http://www.google.com/profiles/bagana.bharatkumar<
>> http://www.google.com/profiles/bagana.bharatkumar>
>> > > *
>> > > Mobile +91 8056127652*
>> > > <bagana.bharatku...@gmail.com>
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > Anup Ghatage
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
