34700

Searching a particular word in a matrix of characters

Question:

I was trying to search for a particular word in a matrix of characters through <strong>C</strong> but was unable to come to a fixed solution.

For ex: Suppose I have to search for the word <strong>INTELLIGENT</strong> in a matrix of characters (3*9) (Once you have picked a character from the matrix to form a sentence, you cannot pick it again to form the same sentence.There is a path from any cell to all its neighboring cells. A neighbor may share an edge or a corner.)

IIIINN.LI ....TTEGL .....NELI

Output: YES (the word INTELLIGENT can be found) Can anybody please give a solution to the above problem !!!!

Answer1:

#include <stdio.h> char Matrix[3][9] = { { 'I','I','I','I','N','N','.','L','I'}, { '.','.','.','.','T','T','E','G','L'}, { '.','.','.','.',',','N','E','L','I'} }; char Choice[3][9] = { { 0 }, { 0 }, { 0 } }; const char WORD[] = "INTELLIGENT"; const int Len = sizeof(WORD)-1; int Path[sizeof(WORD)-1] = { 0 }; char get(int row, int col){ if(1 > col || col > 9) return '\0'; if(1 > row || row > 3) return '\0'; if(Choice[row-1][col-1] || Matrix[row-1][col-1] == '.') return '\0'; else return Matrix[row-1][col-1]; } #define toLoc(r, c) (r)*10+(c) #define getRow(L) L/10 #define getCol(L) L%10 int search(int loc, int level){ int r,c,x,y; char ch; if(level == Len) return 1;//find it r = getRow(loc); c = getCol(loc); ch = get(r,c); if(ch == 0 || ch != WORD[level]) return 0; Path[level]=toLoc(r,c); Choice[r-1][c-1] = 'v';//marking for(x=-1;x<=1;++x){ for(y=-1;y<=1;++y){ if(search(toLoc(r+y,c+x), level + 1)) return 1; } } Choice[r-1][c-1] = '\0';//reset return 0; } int main(void){ int r,c,i; for(r=1;r<=3;++r){ for(c=1;c<=9;++c){ if(search(toLoc(r,c), 0)){ printf("YES\nPath:"); for(i=0;i<Len;++i){ printf("(%d,%d)", getRow(Path[i]), getCol(Path[i])); } printf("\n"); return 0; } } } printf("NO\n"); return 0; }

Answer2:

Use a depth first search.

You can do this using a recursive algorthm. Find all the (unused) places containing the first letter then see if it is possible to find the rest of the word on the remaining board by starting from one of the adjacent squares.

Answer3:

I think this is what you mean..... Though it seems simpler to what you currently have been offered, so I may have misunderstood the question.

I use Numpy to reshape an arbitrary array into a single list of letters, then we create a mask of the search term and a copy of the input list. I tick off each letter to search for while updating the mask.

<pre class="lang-py prettyprint-override"> import numpy as np import copy def findInArray(I,Word): M=[list(x) for x in I] M=list(np.ravel(M)) print "Letters to start: %s"%"".join(M) Mask=[False]*len(Word) T = copy.copy(M) for n,v in enumerate(Word): try: p=T.index(v) except ValueError: pass else: T[p]='' Mask[n]=True print "Letters left over: %s"%"".join(T) if all(Mask):print "Found %s"%Word else:print "%s not Found"%Word print "\n" return all(Mask) I=["IIIINN.LI","....TTEGL",".....NELI"] findInArray(I,"INTEL") findInArray(I,"INTELLIGENT") findInArray(I,"INTELLIGENCE")

<em><strong>Example output</strong></em>

<i> Letters to start: IIIINN.LI....TTEGL.....NELI<br /> Letters left over: IIIN.I....TGL.....NELI<br /> Found INTEL<br /></i>

Letters to start: IIIINN.LI....TTEGL.....NELI<br /> Letters left over: II.I.........NLI<br /> Found INTELLIGENT<br />

Letters to start: IIIINN.LI....TTEGL.....NELI<br /> Letters left over: II.I....T.....NLI<br /> INTELLIGENCE not Found<br />

Answer4:

#include <stdio.h> #define ROW 1 #define COL 11 char Matrix[ROW][COL] = { { 'I','N','T','E','L','L','I','G','E', 'N', 'T'} }; char Choice[ROW][COL] = { { 0 } }; const char WORD[] = "INTELLIGENT"; const int Len = sizeof(WORD)-1; int Path[sizeof(WORD)-1] = { 0 }; char get(int row, int col){ if(1 > col || col > COL) return '\0'; if(1 > row || row > ROW) return '\0'; if(Choice[row-1][col-1] || Matrix[row-1][col-1] == '.') return '\0'; else return Matrix[row-1][col-1]; } #define toLoc(r, c) (r)*16+(c) #define getRow(L) L/16 #define getCol(L) L%16 int search(int loc, int level){ int r,c,x,y; char ch; if(level == Len) return 1;//find it r = getRow(loc); c = getCol(loc); ch = get(r,c); if(ch == 0 || ch != WORD[level]) return 0; Path[level]=toLoc(r,c); Choice[r-1][c-1] = 'v';//marking for(x=-1;x<=1;++x){ for(y=-1;y<=1;++y){ if(search(toLoc(r+y,c+x), level + 1)) return 1; } } Choice[r-1][c-1] = '\0';//reset return 0; } int main(void){ int r,c,i; for(r=1;r<=ROW;++r){ for(c=1;c<=COL;++c){ if(search(toLoc(r,c), 0)){ printf("YES\nPath:"); for(i=0;i<Len;++i){ printf("(%d,%d)", getRow(Path[i]), getCol(Path[i])); } printf("\n"); return 0; } } } printf("NO\n"); return 0; }

Recommend

  • How to style this select element?
  • Compare a column between 2 csv files and write differences using Python
  • href inside href [duplicate]
  • OSStatus error -50 (invalid parameters) AudioQueueNewInput recording audio on iOS
  • How to work with AMMediaType for video filters
  • Programmatically Update Linked Named Range of excel object in MS Word (2007)
  • Arduino making decision according to a packet received from serial port
  • Not able to display correct data in table -AngularJS
  • Invert string in Rust
  • Changing a global variable in C
  • How to unpack 32bit integer packed in a QByteArray?
  • powershell Get-Counter -ComputerName parameter on Windows 7
  • How to read piped content in C?
  • quiver not drawing arrows just lots of blue, matlab
  • std::remove_copy_if_ valgrind bytes in block are possibly lost in loss record
  • gspread or such: help me get cell coordinates (not value)
  • Appending Character to Character Array In C
  • Remove final comma from string in vb.net
  • copying resource to sdcard gives a damaged file in android
  • When to use `image` and when to use `Matrix` in Emgu CV?
  • Why is the size of this struct 32?
  • What is the “return” in scheme?
  • AES padding and writing the ciphertext to a disk file
  • script to move all files from one location to another location
  • ILMerge & Keep Assembly Name
  • Which linear programming package should I use for high numbers of constraints and “warm starts” [clo
  • Symfony2: How to get request parameter
  • Convert array of 8 bytes to signed long in C++
  • How do I use the BLAS library provided by MATLAB?
  • align graphs with different xlab
  • Run Powershell script from inside other Powershell script with dynamic redirection to file
  • Unanticipated behavior
  • using conditional logic : check if record exists; if it does, update it, if not, create it
  • Linker errors when using intrinsic function via function pointer
  • LevelDB C iterator
  • Can't mass-assign protected attributes when import data from csv file
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • How can I use `wmic` in a Windows PE script?
  • Unable to use reactive element in my shiny app
  • How to push additional view controllers onto NavigationController but keep the TabBar?