complete using java are any other computer language software 3. Develop an algor
ID: 3747278 • Letter: C
Question
complete using java are any other computer language software
3. Develop an algorithm to be able to do the word search. Write the algorithm in pseudocode. The word search starts with an nxn square of letters (n rows and n columns stored in an nxn two- dimensional array) and a given word to search. You should search vertically (up/down) and horizontally (left/right) (omit searching diagonally for simplicity) starting from the first letter in the two- dimensional array, continue until either the word is found or the end of the array is reached. You may need to use a stack to help remember which direction has been checked, which has not. The result has to be saved.Explanation / Answer
//Here's the code in C++ :
#include<bits/stdc++.h>
using namespace std;
int n;
char grid[100][100];
int x[] = { -1, 0, 0, 1 };
int y[] = { 0, -1, 1, 0 };
map<pair<pair<int,int>,pair<int,int>>,int> mp;
bool search2D(int row, int col, string word)
{
if (grid[row][col] != word[0])
return false;
int len = word.length();
for (int dir = 0; dir < 4; dir++){
int k, r = row, c = col;
for (k = 1; k < len; k++)
{
r += x[dir], c += y[dir];
if (r >= n || r < 0 || c >= n || c < 0)
break;
if (grid[r][c] != word[k])
break;
}
if (k == len && !mp[make_pair(make_pair(r,c),make_pair(row,col))]){
mp[make_pair(make_pair(row,col),make_pair(r,c))]=1;
return true;
}
}
return false;
}
void patternSearch(string word)
{
for (int row = 0; row < n; row++)
for (int col = 0; col < n; col++)
search2D(row, col, word);
}
int main()
{
cin>>n;
for (int row = 0; row < n; row++)
for (int col = 0; col < n; col++)
cin>>grid[row][col];
string word;
cin>>word;
patternSearch(word);
for(auto i:mp)
if(i.second)
cout<<i.first.first.first<<","<<i.first.first.second<<" -> "<<i.first.second.first<<","<<i.first.second.second<<endl;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.