Skip to content

Instantly share code, notes, and snippets.

@azihassan

azihassan/bfs.cpp

Created December 30, 2016 20:39
Show Gist options
  • Save azihassan/884be457861fe80c060728a0b5c90501 to your computer and use it in GitHub Desktop.
Save azihassan/884be457861fe80c060728a0b5c90501 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bfs.cpp
#include <iostream>
#include <algorithm>
#include <array>
#include <utility>
#include <map>
#include <vector>
#include <queue>
struct Point
{
int x;
int y;
Point(int x, int y) : x(x), y(y) {}
bool operator<(const Point& p) const
{
return x == p.x ? y < p.y : x < p.x;
}
bool operator==(const Point& p) const
{
return x == p.x && y == p.y;
}
Point operator+(const Point& p) const
{
return Point(x + p.x, y + p.y);
}
};
int bfs(const std::vector<std::vector<int>>& grid, const Point& start, const Point& end);
void draw_grid(const std::vector<std::vector<int>>& grid, const std::vector<Point>& path);
int main()
{
/*std::vector<std::vector<int>> grid {
{1, 2, 1, 1},
{1, 1, 2, 0},
{0, 0, 1, 0},
{1, 1, 1, 1},
{0, 0, 0, 1},
};*/
std::vector<std::vector<int>> grid {
{1, 2, 1, 1, 2, 1},
{1, 1, 2, 1, 1, 1},
{0, 1, 1, 2, 2, 0},
{1, 1, 1, 2, 1, 1},
{0, 1, 1, 2, 2, 1},
};
Point start(0, 0), end(5, 4);
std::cout << bfs(grid, start, end) << std::endl;
std::cout << "Done !" << std::endl;
}
void draw_grid(const std::vector<std::vector<int>>& grid, const std::vector<Point>& path)
{
for(size_t y = 0; y < grid.size(); y++)
{
for(size_t x = 0; x < grid[0].size(); x++)
{
if(std::find(path.begin(), path.end(), Point(x, y)) == path.end())
std::cout << ' ' << grid[y][x] << ' ';
else
std::cout << '[' << grid[y][x] << ']';
}
std::cout << std::endl;
}
}
int bfs(const std::vector<std::vector<int>>& grid, const Point& start, const Point& end)
{
std::queue<std::vector<Point>> queue;
std::vector<std::vector<Point>> visited;
std::map<std::pair<Point, Point>, int> distances;
std::vector<Point> tmp {start};
queue.push(tmp);
visited.push_back(tmp);
distances[std::make_pair(start, start)] = 0;
int min = INT_MAX;
while(!queue.empty())
{
std::vector<Point> top = queue.front();
queue.pop();
if(top.back() == end)
{
int dist = 0;
for(auto& p: top)
dist += grid[p.y][p.x];
dist--;
std::cout << dist << std::endl;
draw_grid(grid, top);
min = std::min(dist, min);
std::cout << std::endl;
}
std::array<Point, 2> moves {
Point(0, 1),
Point(1, 0)
};
for(const auto& move: moves)
{
auto dest = top;
dest.push_back(top.back() + move);
if(dest.back().x >= grid[0].size() || dest.back().y >= grid.size())
continue;
if(grid[dest.back().y][dest.back().x] == 0)
continue;
if(std::find(visited.begin(), visited.end(), dest) != visited.end())
continue;
visited.push_back(dest);
distances[std::make_pair(start, dest.back())] = distances[std::make_pair(start, top.back())] + grid[dest.back().y][dest.back().x];
queue.push(dest);
}
}
return min;
}
Raw
output.txt
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1] 1 2 2 0
1 [1] 1 2 1 1
0 [1][1][2][2][1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1] 2 1 1
0 1 [1][2][2][1]
12
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2] 1 1
0 1 1 [2][2][1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2][1] 1
0 1 1 2 [2][1]
10
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2][1][1]
0 1 1 2 2 [1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1] 2 1 1
0 1 [1][2][2][1]
12
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2] 1 1
0 1 1 [2][2][1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2][1] 1
0 1 1 2 [2][1]
10
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2][1][1]
0 1 1 2 2 [1]
13
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
12
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
12
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1][2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
11
[1] 2 1 1 2 1
[1][1] 2 1 1 1
0 [1][1][2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
12
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1] 2 1 1
0 1 [1][2][2][1]
13
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2] 1 1
0 1 1 [2][2][1]
12
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1] 1
0 1 1 2 [2][1]
11
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1][1]
0 1 1 2 2 [1]
14
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
13
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
12
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
13
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1] 2 1 1 2 1
[1][1][2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
14
[1] 2 1 1 2 1
[1][1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
13
[1] 2 1 1 2 1
[1][1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
12
[1] 2 1 1 2 1
[1][1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
13
[1] 2 1 1 2 1
[1][1][2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1] 2 1 1 2 1
[1][1][2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
12
[1] 2 1 1 2 1
[1][1][2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
11
[1] 2 1 1 2 1
[1][1][2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1] 1 2 2 0
1 [1] 1 2 1 1
0 [1][1][2][2][1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1] 2 1 1
0 1 [1][2][2][1]
13
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2] 1 1
0 1 1 [2][2][1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2][1] 1
0 1 1 2 [2][1]
11
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1] 1 2 2 0
1 [1][1][2][1][1]
0 1 1 2 2 [1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1] 2 1 1
0 1 [1][2][2][1]
13
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2] 1 1
0 1 1 [2][2][1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2][1] 1
0 1 1 2 [2][1]
11
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1] 2 2 0
1 1 [1][2][1][1]
0 1 1 2 2 [1]
14
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
13
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1][2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
13
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1][2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1][2] 1 1 2 1
1 [1] 2 1 1 1
0 [1][1][2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
13
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1] 2 1 1
0 1 [1][2][2][1]
14
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2] 1 1
0 1 1 [2][2][1]
13
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1] 1
0 1 1 2 [2][1]
12
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1][1]
0 1 1 2 2 [1]
15
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
14
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
13
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
14
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
13
[1][2] 1 1 2 1
1 [1][2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
15
[1][2] 1 1 2 1
1 [1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
14
[1][2] 1 1 2 1
1 [1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
13
[1][2] 1 1 2 1
1 [1][2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
14
[1][2] 1 1 2 1
1 [1][2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
13
[1][2] 1 1 2 1
1 [1][2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
13
[1][2] 1 1 2 1
1 [1][2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1][2] 1 1 2 1
1 [1][2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
13
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1] 2 2 0
1 1 [1] 2 1 1
0 1 [1][2][2][1]
14
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2] 1 1
0 1 1 [2][2][1]
13
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1] 1
0 1 1 2 [2][1]
12
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1] 2 2 0
1 1 [1][2][1][1]
0 1 1 2 2 [1]
15
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
14
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
13
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1][2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
14
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
13
[1][2][1] 1 2 1
1 1 [2] 1 1 1
0 1 [1][2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
15
[1][2][1] 1 2 1
1 1 [2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
14
[1][2][1] 1 2 1
1 1 [2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
13
[1][2][1] 1 2 1
1 1 [2][1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
14
[1][2][1] 1 2 1
1 1 [2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
13
[1][2][1] 1 2 1
1 1 [2][1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
13
[1][2][1] 1 2 1
1 1 [2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1][2][1] 1 2 1
1 1 [2][1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
14
[1][2][1][1] 2 1
1 1 2 [1] 1 1
0 1 1 [2] 2 0
1 1 1 [2] 1 1
0 1 1 [2][2][1]
13
[1][2][1][1] 2 1
1 1 2 [1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1] 1
0 1 1 2 [2][1]
12
[1][2][1][1] 2 1
1 1 2 [1] 1 1
0 1 1 [2] 2 0
1 1 1 [2][1][1]
0 1 1 2 2 [1]
13
[1][2][1][1] 2 1
1 1 2 [1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1][2][1][1] 2 1
1 1 2 [1] 1 1
0 1 1 [2][2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
12
[1][2][1][1] 2 1
1 1 2 [1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
11
[1][2][1][1] 2 1
1 1 2 [1][1] 1
0 1 1 2 [2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
13
[1][2][1][1][2] 1
1 1 2 1 [1] 1
0 1 1 2 [2] 0
1 1 1 2 [1] 1
0 1 1 2 [2][1]
12
[1][2][1][1][2] 1
1 1 2 1 [1] 1
0 1 1 2 [2] 0
1 1 1 2 [1][1]
0 1 1 2 2 [1]
10
Done !
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment