top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

String Path in Matrix ?

+5 votes
293 views

How to implement a function to check whether there is a path for a string in a matrix of characters? It moves to left, right, up and down in a matrix, and a cell for a movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.

posted Dec 12, 2013 by Gaurav Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

A path is defined as a stack. When a cell on path is found, we push its position into the stack. Additionally, we also define a matrix of Boolean masks to void entering a cell twice, which is denoted as visited. Based on these considerations, the skeleton of solution can be implemented as the following:

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
        return false;
    bool *visited = new bool[rows * cols];
    memset(visited, 0, rows * cols);

    for(int row = 0; row < rows; ++row)
    {
        for(int column = 0; column < cols; ++column)
        {
            if(matrix[row * cols + column] != str[0])
                continue;
            std::stack<Position> path;
            Position position = {column, row};
            path.push(position);
            visited[row * cols + column] = true;
            if(hasPathCore(matrix, rows, cols, str, path, visited))
                return true;
        }
    }

    return false;
}

Now let us analyze how to explore a path in details. Supposing we have already found k characters on a path, and we are going to explore the next step. We stand at the cell corresponding to the kth character of the path, and check whether the character in its neighboring cell at up, right, down, and left side is identical to the (k+1)th character of the string.

If there is a neighboring cell whose value is identical to the (k+1)th character of the string, we continue exploring the next step.

If there is no such a neighboring cell whose value is identical to the (k+1)th character of the string, it means the cell corresponding to the kth character should not on a path. Therefore, we pop it off a path, and start to explore other directions on the (k-1)th character.

Based on the analysis above, the function hasPathCore can be defined as:

bool hasPathCore(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
    if(str[path.size()] == '\0')
        return true;

    if(getNext(matrix, rows, cols, str, path, visited, 0))
        return hasPathCore(matrix, rows, cols, str, path, visited);

    bool hasNext = popAndGetNext(matrix, rows, cols, str, path, visited);
    while(!hasNext && !path.empty())
        hasNext = popAndGetNext(matrix, rows, cols, str, path, visited);

    if(!path.empty())
        return hasPathCore(matrix, rows, cols, str, path, visited);
     return false;
}

Check this : BOOK

answer Dec 19, 2013 by Satyabrata Mahapatra
Similar Questions
+7 votes

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11      

0       16      23      31      16      7

67      5       4       23      21      19

Answer

1       6       8       9       0  ----> 3
                                         |
4       9       -5      5       11      13
                                         |
8       9       44      23      15      -20
                                         |
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11     
|
0       16      23      31      16        7

67      5       4       23      21       19
+5 votes
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
+6 votes

Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s.

...