?
nun mit code formatierung:
#include <iostream>
#include <string>
#include <cassert>
#include <vector>
#include <queue>
using namespace std;
class pos {
public:
int row;
int col;
pos(): row(0), col(0) {}
pos(int r, int c): row(r), col(c) {}
pos &operator=(pos p) {
swap(row, p.row);
swap(col, p.col);
return *this;
}
pos operator+(const pos p) {
pos result = *this;
result.row += p.row;
result.col += p.col;
return result;
}
bool operator==(const pos &p) {
return row == p.row && col == p.col;
}
};
void print(vector<vector<int>> &vec) {
for (int i = 0; i < vec.size(); i++) {
for (int j = 0; j < vec[0].size(); j++) {
cout << vec[i][j] << " ";
}
cout << '\n';
}
}
bool check_boundary(vector<vector<int>> &vec, pos curr) {
if (curr.row < 0 || (curr.row >= vec.size())) {
return false;
}
if (curr.col < 0 || (curr.col >= vec[0].size())) {
return false;
}
return true;
}
bool is_valid_move(vector<vector<int>> &vec, vector<vector<int>> &visited, pos curr) {
if (!check_boundary(vec, curr)) {
return false;
}
if (vec[curr.row][curr.col] == 0) {
return false;
}
return true;
}
void cleanup_path(vector<pos> &path, pos curr, pos start) {
if (path.size() < 2) {
return;
}
pos prev_pos = curr;
auto it = path.end() - 2;
while (it != path.begin()) {
bool can_move = false;
vector<pos> moveVec = {pos(0,-1), pos(0,1), pos(-1,0), pos(1,0)};
for (auto &m: moveVec) {
pos next_pos = prev_pos + m;
if (*it == next_pos) {
can_move = true;
}
}
if (!can_move) {
auto next = it-1;
path.erase(it);
it = next;
}
else {
prev_pos = *it;
it--;
}
}
}
bool bfs(vector<vector<int>> &vec, vector<vector<int>> &visited, pos start, pos dest, vector<pos> &path) {
queue<pos> q;
q.push(start);
while (!q.empty()) {
pos curr = q.front();
q.pop();
if (visited[curr.row][curr.col] == 1) {
continue;
}
visited[curr.row][curr.col] = 1;
path.push_back(curr);
if (curr == dest) {
cleanup_path(path, curr, start);
return true;
}
bool can_move = false;
// left right up down
vector<pos> moveVec = {pos(0,-1), pos(0,1), pos(-1,0), pos(1,0)};
for (auto &m: moveVec) {
pos next_pos = curr + m;
if (is_valid_move(vec, visited, next_pos)) {
can_move = true;
q.push(next_pos);
}
}
if (!can_move) {
//cout << "pop_back" << endl;
path.pop_back();
visited[curr.row][curr.col] = 0;
}
}
return false;
}
bool find_shortest_path(vector<vector<int>> &vec, pos start, pos dest) {
vector<pos> path;
vector<vector<int>> visited;
visited.resize(vec.size(), vector<int>(vec[0].size(), 0));
bool res = bfs(vec, visited, start, dest, path);
for (auto &p: path) {
cout << "row: " << p.row << ",col: " << p.col << endl;
}
return res;
}
int main() {
vector<vector<int>> vec = {{1,0,1,1,1},
{1,1,1,0,1},
{1,0,0,1,1},
{1,0,0,1,0},
{1,0,0,1,1}};
cout << find_shortest_path(vec, pos(0,0), pos(4,2)) << endl;
return 0;
}
