Как найти кратчайший путь от A до B на сетке?

В моем упражнении мне нужно найти кратчайший путь от одной точки к другой на матрице, и на пути есть некоторые препятствия. Я использую код C++.Как найти кратчайший путь от A до B на сетке?

Например:

X X X X X X X X 

X X X 4 X X 3 X 

X X 8 X X X X X 

0 X X X X 6 X X

Если мне нужно получить от местоположения холдинга в месте, проведение , я знаю, что я должен идти шесть шагов вправо и два шага вверх , Но в моем упражнении я не могу пройти еще один номер; путь должен использовать только местоположения, отмеченные знаком X.

Я попытался написать рекурсивную функцию для решения этой проблемы, но она не работает.

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

Вот код, который я написал:

int Rec(Point start, Point finish,Direction dira) 
{ 
    int up = 0, down = 0, left = 0, right = 0; 
    int res; 
    Point tmp; 
    if (finish.getX() == start.getX() && finish.getY()==start.getY()) 
     return 0; 
    else if (dira == UP) 
    { 
     tmp = start; 
     tmp.setY(start.getY() - 1); 
     if (screen->getBoardChar(tmp) == ' '){ 
      up++; 
      up += Rec(tmp, finish, UP); 
     }  
     tmp = start; 
     tmp.setX(start.getX() + 1); 
     if (screen->getBoardChar(tmp) == ' '){ 
      right++; 
      right += Rec(tmp, finish, RIGHT); 
     }  
     tmp = start; 
     tmp.setX(start.getX() - 1); 
     if (screen->getBoardChar(tmp) == ' '){ 
      left += Rec(tmp, finish, LEFT); 
      left++; 
     } 
    } 
    else if (dira == DOWN) 
    { 
     tmp = start; 
     tmp.setY(start.getY() + 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      down++; 
      down += Rec(tmp, finish, DOWN); 
     } 
     tmp = start; 
     tmp.setX(start.getX() + 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      right++; 
      right += Rec(tmp, finish, RIGHT); 
     } 
     tmp = start; 
     tmp.setX(start.getX() - 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      left += Rec(tmp, finish, LEFT); 
      left++; 
     } 
    } 
    else if (dira == LEFT) 
    { 
     tmp = start; 
     tmp.setY(start.getY() + 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      down++; 
      down += Rec(tmp, finish, DOWN); 
     } 
     tmp = start; 
     tmp.setX(start.getX() - 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      left += Rec(tmp, finish, LEFT); 
      left++; 
     } 
     tmp = start; 
     tmp.setY(start.getY() - 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      up++; 
      up += Rec(tmp, finish, UP); 
     } 
    } 
    else 
    { 
     tmp = start; 
     tmp.setY(start.getY() + 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      down++; 
      down += Rec(tmp, finish, DOWN); 
     } 
     tmp = start; 
     tmp.setY(start.getY() - 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      up++; 
      up += Rec(tmp, finish, UP); 
     } 
     tmp = start; 
     tmp.setX(start.getX() + 1); 
     if (screen->getBoardChar(tmp) == ' ') { 
      right++; 
      right += Rec(tmp, finish, RIGHT); 
     } 
    } 
    res = Smallest(up, down, left, right); 
    return res; 
}

источник

2017-01-14 Gal Zaken

Я попытался уточнить ваше название и текст вашего вопроса. Было бы полезно точно знать, что вы имеете в виду, когда говорите, что ваш код не работает. –

Привет, проблема в том, что rec dont realy дает мне исправить количество шагов .. я не знаю больше, чем; / –

Его легко у вас есть две позиции, где вы сейчас, и где вам нужно идти, так что вы делаете в то время как петли, пока вы не получите на правой х, а затем сделайте while loop, пока не достигнете правого y. вам также нужно знать направление ведьмы, чтобы вы вычислили, что тоже его не жесткий эфир

int char[4][8] = { values }; 
int fromnum;// from witch number 
int tonum;// to number 
int fromx, fromy;//from coordinates 
int tox,toy; // to coordinates 
for (int i = 0; i < 4; i++) { 
    for (int a = 0; a < 8; a++) { 
     //find a cordinates of your start and end point 
    } 
} 

// when you know cordinates you can just supstract them and you will know the path

источник

2017-01-14 17:16:00 yahoo5000

Как найти кратчайший путь от A до B на сетке?

ответ

Смежные вопросы