No. 34 - String Path in Matrix
Question: 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.
For example, the matrix below with three rows and four columns has a path for the string “BCCED” (as highlighted in the matrix). It does not have a path for the string “ABCB”, because the first “B” in the string occupies the “B” cell in the matrix, and the second “B” in the string cannot enter into the same cell again.
A
|
B
|
C
|
E
|
S
|
F
|
C
|
S
|
A
|
D
|
E
|
E
|
Analysis: It is a typical problem about backtracking, which can be solved by storing a path into a stack.
Firstly, it is necessary to define a structure for 2-D positions, as below:
struct Position
{
int x;
int y;
};
The movements of four directions can be defined accordingly:
Position up = {0, -1};
Position right = {1, 0};
Position down = {0, 1};
Position left = {-1, 0};
Position dir[] ={up, right, down, left};
Since paths can start from any entry in a matrix, we have to scan every cell to check whether the character in it is identical to the first character of the string. If it is identical, we begin to explore a path from such a cell.
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 kcharacters 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;
}
The function getNext is defined to explore the (k+1)th character on a path. When it returns true, it means the (k+1)th character on a path has been found. Otherwise, we have to pop the kthcharacter off. The function getNext is implemented as below:
bool getNext(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited, int start)
{
for(int i = start; i < sizeof(dir) / sizeof(Position); ++i)
{
Position next = {path.top().x + dir[i].x, path.top().y + dir[i].y};
if(next.x >= 0 && next.x < cols
&& next.y >=0 && next.y < rows
&& matrix[next.y * cols + next.x] == str[path.size()]
&& !visited[next.y * cols + next.x])
{
path.push(next);
visited[next.y * cols + next.x] = true;
return true;
}
}
return false;
}
When we found that the kth character should not be on a path, we call the functionpopAndGetNext to pop it off, and try on other directions from the (k-1)th character. This function is implemented as below:
bool popAndGetNext(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
Position toBePoped = path.top();
path.pop();
visited[toBePoped.y * cols + toBePoped.x] = false;
bool hasNext = false;
if(path.size() >= 1)
{
Position previous = path.top();
int deltaX = toBePoped.x - previous.x;
int deltaY = toBePoped.y - previous.y;
for(int i = 0; (i < sizeof(dir) / sizeof(Position) && !hasNext); ++i)
{
if(deltaX != dir[i].x || deltaY != dir[i].y)
continue;
hasNext = getNext(matrix, rows, cols, str, path, visited, i + 1);
}
}
return hasNext;
}
No comments:
Post a Comment