Post date: Jul 07, 2013 11:31:13 PM
Problem
* String [] [] matrix = {{"A","N", "L", "Y", "S"},{"I", "S", "D", "E", "S"},{"I", "G", "N", "D", "E"}};
// 2. Given a word "DES"
// 3. Write a program to find the occurences of this word "DES". Letters must be next to each other in the matric.
// 4. "Next" means: left, right, up, down, left down, right down, upper left, upper right
// 5.. For example: S at (1,1): A, N, L, D, N, G, I, I are next to S at (1,1)
Required output
// D - [1, 2], E - [1, 3], S- [1, 4]
// D - [1, 2], E - [1, 3], S- [0, 4]
// D - [2, 3], E - [2, 4], S - [1, 4]
// D - [2, 3], E - [1, 3], S - [0, 4]
// D - [2, 3], E - [1, 3], S - [1, 4]
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the occurences of a specified word in a matrix -- Amazon
Created Date : 08-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;
enum Direction { Left, Right, Up, Down, LeftDown, RightDown, UpperLeft, UpperRight };
bool IsValidPosition(int rows, int cols, pair<int, int> pt)
{
if(pt.first < 0 || pt.first >= rows) return false;
if(pt.second < 0 || pt.second >= cols) return false;
return true;
}
pair<int, int>& GoNext(pair<int, int>& pt, Direction dir, pair<int, int>& next)
{
pair<int, int> displacements[] = {
make_pair( 0, -1),
make_pair( 0, 1),
make_pair(-1, 0),
make_pair( 1, 0),
make_pair(-1, -1),
make_pair( 1, -1),
make_pair(-1, 1),
make_pair( 1, 1)
};
next.first = pt.first + displacements[(int)dir].first;
next.second = pt.second + displacements[(int)dir].second;
return next;
}
static void MoveNext(char* matrix, int rows, int cols, string word, pair<int, int>& pt, int step, vector<pair<int, int>>& path)
{
if(step == word.size() - 1)
{
int i = 0;
for(int i = 0; i < word.size(); ++i)
{
cout << word[i] << "[";
cout << path[i].first << ", ";
cout << path[i].second << "] ";
}
cout << endl;
return;
}
for(int it = Left; it <= UpperRight; ++it){
pair<int, int> next;
GoNext(pt, (Direction)it, next);
if (IsValidPosition(rows, cols, next) && matrix[next.first * cols + next.second] == word[step + 1])
{
path.push_back(next);
MoveNext(matrix, rows, cols, word, next, step + 1, path);
path.pop_back();
}
}
}
static void ComputeWordOccurence(char* matrix, int rows, int cols, string word)
{
vector<pair<int, int>> path;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (matrix[i * cols + j] == word[0])
{
path.push_back(make_pair(i, j));
MoveNext(matrix, rows, cols, word, make_pair(i, j), 0, path);
path.pop_back();
}
}
}
}
static void DoTest(char* matrix, int rows, int cols, string word)
{
cout << "The matrix is :" << endl;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
cout << setw(3) << matrix[i * cols + j];
}
cout << endl;
}
cout << endl;
cout << "The word to find is : " << word << endl;
cout << endl;
cout << "The output is :" << endl;
ComputeWordOccurence(matrix, rows, cols, word);
cout << endl;
}
int main(int argc, char* argv[])
{
char matrix[3][5] = {
{ 'A', 'N', 'L', 'Y', 'S' },
{ 'I', 'S', 'D', 'E', 'S' },
{ 'I', 'G', 'N', 'D', 'E' } };
string word = "DES";
DoTest(&matrix[0][0], 3, 5, word);
return 0;
}
Output
The matrix is :
A N L Y S
I S D E S
I G N D E
The word to find is : DES
The output is :
D[1, 2] E[1, 3] S[1, 4]
D[1, 2] E[1, 3] S[0, 4]
D[2, 3] E[1, 3] S[1, 4]
D[2, 3] E[1, 3] S[0, 4]
D[2, 3] E[2, 4] S[1, 4]
Press any key to continue . . ..