график, чтобы найти кратчайший путь к источнику, используя узлы, которые я посетил - PullRequest
Новая
       54

график, чтобы найти кратчайший путь к источнику, используя узлы, которые я посетил

0 голосов
/ 28 апреля 2020

Учитывая направления и маршрут, я хочу знать кратчайший путь, чтобы, в конце концов, вернуться туда, откуда я начал (начало координат), только используя места, которые я посетил до

(пример изображения ниже, N - север, S - юг и др. c)

Пример ввода: NNEEEENWNENNSEEE WWWSWSESWWWNNNNWWWSSNNNNEE

Пример вывода: 14

изображение с примером, красный является кратчайшим путем и дает 14 выходных данных

Я работаю в java и хочу использовать алгоритм поиска в ширину и хочу использовать график, который является лучшим способом, которым я могу построить это график и посмотрите эту проблему?

Может кто-нибудь помочь?

Ответы [ 2 ]

0 голосов
/ 28 апреля 2020

Просто запустите BFS, начиная с конца и переходя к уже пройденным позициям, останавливаясь, как только вы достигнете исходной позиции: 

#include <bits/stdc++.h>
using namespace std;

int m[9][10];
int v[9][10];

struct point{
    int x, y, dist;
    point(){}
    point(int x, int y){this->x = x; this->y = y; dist = 0;}
    point(int x, int y, int dist){this->x = x; this->y = y; this->dist = dist;}
    bool operator == (const point &rhs) const { return rhs.x == x && rhs.y == y; }
};

point origin(2, 8);
point target(2, 0);

int BFS(){
    queue<point> q;
    q.push(target);
    while(!q.empty()){
        point p = q.front();
        q.pop();
        v[p.y][p.x] = 1;
        if(p == origin) return p.dist;

        if(p.x > 0 && !v[p.y][p.x - 1] && m[p.y][p.x - 1]) q.push(point(p.x - 1, p.y, p.dist + 1)); //left
        if(p.x < 9 && !v[p.y][p.x + 1] && m[p.y][p.x + 1]) q.push(point(p.x + 1, p.y, p.dist + 1)); //right
        if(p.y > 0 && !v[p.y - 1][p.x] && m[p.y - 1][p.x]) q.push(point(p.x, p.y - 1, p.dist + 1)); //up
        if(p.y < 8 && !v[p.y + 1][p.x] && m[p.y + 1][p.x]) q.push(point(p.x, p.y + 1, p.dist + 1)); //down
    }
    return -1;
}

int main(){
    memset(m, 0, sizeof(m));
    memset(v, 0, sizeof(v));
    m[origin.y][origin.x] = 1;

    string path = "NNEEEENWNENNSEEEWWWSWSESWWWNNNNWWWSSNNNNEE";

    point o(origin.x, origin.y);

    for(int i = 0; i < path.size(); i++){
        if(path[i] == 'N') o.y--;
        else if(path[i] == 'S') o.y++;
        else if(path[i] == 'W') o.x--;
        else if(path[i] == 'E') o.x++;
        m[o.y][o.x] = 1;
    }

    cout<<"dist = "<<BFS()<<endl;
}

OUTPUT: dist = 14 .

0 голосов
/ 28 апреля 2020

Вы можете сгенерировать график посещенных ячеек, прочитав входные данные, а затем запустить BFS на этом графике с последней позиции.

Чтобы сгенерировать график, вы можете сделать: 

for each direction :
   create node for the cell if not already existing
   for each adjacent cell, if visited then connect them together
...