Instrumenting path
#include <iostream>
#include <queue>
class node { public: int x, y; };
int bfs(int x, int y)
{
node start;
int result = 0;
start.x = x;
start.y = y;
std::queue<node> search_queue;
bool visited[4][4];
int map[4][4] =
{
{0, 1, 0, 1},
{0, 0, 0, 0},
{1, 0, 1, 0},
{0, 1, 0, 0}
};
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
visited[i][j] = false;
}
}
search_queue.push(start);
while (!search_queue.empty())
{
node top = search_queue.front();
search_queue.pop();
if (visited[top.x][top.y])
continue;
if (map[top.x][top.y] == 1)
continue;
if (top.x < 0 || top.x >= 4)
continue;
if (top.y < 0 || top.y >= 4)
continue;
visited[top.x][top.y] = true;
std::cout << "visit: [" << top.x << "][" << top.y << "]\n";
result++;
node temp;
temp.x = top.x + 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x - 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y + 1;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y - 1;
search_queue.push(temp);
}
return result;
}
int main()
{
std::cout << bfs(0, 0);
}
produces:
visit: [0][0]
visit: [1][0]
visit: [1][1]
visit: [2][1]
visit: [1][2]
visit: [0][2]
visit: [1][3]
visit: [2][3]
visit: [3][3]
visit: [3][2]
10
One interesting point is that it reaches [3][3]
and continues; you don't seem to have the end well defined. That accounts for one of the extra count (compared with the 7 that should be expected). The [2][1]
and [0][2]
dead-ends account for the other two. Basically, you need to decrement result
when you follow a dead-end and reach the end.
Designating end point
Bounds checking changed after seeing answer by iavr.
#include <iostream>
#include <queue>
class node { public: int x, y; };
int bfs(int bx, int by, int ex, int ey)
{
node start;
int result = 0;
start.x = bx;
start.y = by;
std::queue<node> search_queue;
bool visited[4][4];
int map[4][4] =
{
{0, 1, 0, 1},
{0, 0, 0, 0},
{1, 0, 1, 0},
{0, 1, 0, 0}
};
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
visited[i][j] = false;
}
}
search_queue.push(start);
while (!search_queue.empty())
{
node top = search_queue.front();
search_queue.pop();
if (top.x < 0 || top.x >= 4)
continue;
if (top.y < 0 || top.y >= 4)
continue;
if (visited[top.x][top.y])
continue;
if (map[top.x][top.y] == 1)
continue;
visited[top.x][top.y] = true;
std::cout << "visit: [" << top.x << "][" << top.y << "]\n";
result++;
if (top.x == ex && top.y == ey)
break;
node temp;
temp.x = top.x + 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x - 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y + 1;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y - 1;
search_queue.push(temp);
}
return result;
}
int main()
{
std::cout << bfs(0, 0, 3, 3);
}
Output:
visit: [0][0]
visit: [1][0]
visit: [1][1]
visit: [2][1]
visit: [1][2]
visit: [0][2]
visit: [1][3]
visit: [2][3]
visit: [3][3]
9
Getting the correct answer
#include <iostream>
#include <queue>
class node { public: int x, y, l; };
int bfs(int bx, int by, int ex, int ey)
{
node start;
int result = 0;
start.x = bx;
start.y = by;
start.l = 1;
std::queue<node> search_queue;
bool visited[4][4];
int map[4][4] =
{
{0, 1, 0, 1},
{0, 0, 0, 0},
{1, 0, 1, 0},
{0, 1, 0, 0}
};
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
visited[i][j] = false;
}
}
search_queue.push(start);
while (!search_queue.empty())
{
node top = search_queue.front();
search_queue.pop();
if (visited[top.x][top.y])
continue;
if (map[top.x][top.y] == 1)
continue;
if (top.x < 0 || top.x >= 4)
continue;
if (top.y < 0 || top.y >= 4)
continue;
visited[top.x][top.y] = true;
std::cout << "visit: [" << top.x << "][" << top.y << "] = " << top.l << "\n";
result = top.l;
if (top.x == ex && top.y == ey)
break;
node temp;
temp.l = top.l + 1;
temp.x = top.x + 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x - 1;
temp.y = top.y;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y + 1;
search_queue.push(temp);
temp.x = top.x;
temp.y = top.y - 1;
search_queue.push(temp);
}
return result;
}
int main()
{
std::cout << bfs(0, 0, 3, 3) << std::endl;
}
Output:
visit: [0][0] = 1
visit: [1][0] = 2
visit: [1][1] = 3
visit: [2][1] = 4
visit: [1][2] = 4
visit: [0][2] = 5
visit: [1][3] = 5
visit: [2][3] = 6
visit: [3][3] = 7
7