3. maze solving algo

maze solving algo

  • ?

    Hi,

    kann mir jemand kurzes feedback zu meinem maze solving algo geben? ich weiss man koennte auch sowas wie A* implementieren... ich hatte mich fuer BFS entschieden um auch den shortest path zu bekommen...

    beschreibung:
    A Maze is given as M*N binary matrix of blocks with a source block a and destination block. A rat starts from source and has to reach destination. The rat can move only in two directions: left, right, up and down.
    In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination.

    #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();

    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,4)) << endl;

    return 0;
    }

    0
  • ?

    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;
}
    0
Anmelden zum Antworten