1. Problem Description
The original problem is from a Microsoft Interview Question on careercup.
"Consider a MxN matrix. You are given a start element(index) and an end element. The question is to find a path from start to end. Please note that in some blocks 'X' is marked which means your path cannot go through that element. My solution was to have a tree with 4 nodes (top/left/right/bottom) and recursively check if there is a path from start to end."
2. Solution
Use breath first search to explore the neighbors of the current location,which begins from the start location. The explored area expands outwards in each direction (north, south, west and east). The explored grid becomes either blocked or visited. If it expands to the destination grid eventually, then it returns true to indicate there is a path from the start to end grid. Otherwise return false to indicate there is no path.
I was thinking of using the tree structure to model the road map (grids), as most contributors on this thread, a Microsoft Interview Question on careercup. But later I abandoned this idea because I think it is not an efficient solution in memory wise. In order to quickly prototype the solution, I choose the matrix/vector to describe the road map and its value can indicated blocked/non-blocked or even the length of the road. As the size of the road map grows, a better choice might be use linked-list (see my 4 blogs about linked list here, Part I, Part II, Part III, and Part IV.) to describe sparse matrix.
3. C++ Implementation
Really simple and straightforward implementation, a few dozens line of code. Welcome any good ideas on the road map for the testing.
// Implementation
//********************************************************************************
#include <queue>
#include <vector>
#include <assert.h>
struct Position {
unsigned int row;
unsigned int col;
Position(unsigned int posR = 0,
unsigned int posC = 0)
: row(posR), col(posC)
{}
bool operator==(const Position& rhs) const
{
return row == rhs.row && col == rhs.col;
}
};
// Road Map for each Grid
// 0 - available path
// 1- blocked
// 2 - visited (not available for later search)
bool PathFinder(const Position& start,
const Position& end,
std::vector<std::vector<unsigned char>>& roadMap,
const unsigned int MATRIX_ROW,
const unsigned int MATRIX_COL)
{
if (start.row >= MATRIX_ROW || start.col >= MATRIX_COL ||
end.row >= MATRIX_ROW || end.col >= MATRIX_COL) {
return false;
}
if (roadMap[start.row][start.col] == 1 ||
roadMap[end.row][end.col] == 1) {
return false;
}
std::queue<Position> posToVisit;
posToVisit.push(start);
while (!posToVisit.empty()) {
const Position curPos = posToVisit.front();
// found the path
if (curPos == end) {
return true;
}
// Position in the corodinate of row and col
// (row = 0, col = 0) in the northwest corner
// (row = MATRIX_ROW, rol = MATRIX_COL) in the southeast corner
if (curPos.row > 0) {
Position northPos{ curPos.row - 1, curPos.col };
if (roadMap[northPos.row][northPos.col] == 0) { // available path
posToVisit.push(northPos);
}
}
if (curPos.row < (MATRIX_ROW - 1)) {
Position southPos{ curPos.row + 1, curPos.col };
if (roadMap[southPos.row][southPos.col] == 0) {// available path
posToVisit.push(southPos);
}
}
if (curPos.col > 0) {
Position westPos{ curPos.row, curPos.col - 1 };
if (roadMap[westPos.row][westPos.col] == 0) {// available path
posToVisit.push(westPos);
}
}
if (curPos.col < (MATRIX_COL - 1)) {
Position eastPos{ curPos.row, curPos.col + 1 };
if (roadMap[eastPos.row][eastPos.col] == 0) {// available path
posToVisit.push(eastPos);
}
}
// mark this grid as visited
roadMap[curPos.row][curPos.col] = 2;
posToVisit.pop();
}
return false;
}
//********************************************************************************
// Test
//********************************************************************************
void TestPass_1()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestPass_2()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestPass_3()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestPass_4()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 1, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestPass_5()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestPass_6()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == true);
}
void TestFail_1()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_2()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_3()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_4()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_5()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_6()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
void TestFail_7()
{
const unsigned int MATRIX_ROW = 10;
const unsigned int MATRIX_COL = 10;
std::vector<std::vector<unsigned char>> roadMap =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
bool found = PathFinder(Position{ 0, 0 },
Position{ 9, 9 },
roadMap,
MATRIX_ROW,
MATRIX_COL
);
assert(found == false);
}
//********************************************************************************
No comments:
Post a Comment