Задачи со пронаоѓање пат.

Здраво може некој да ми помогне околу овој вид на задачи? Барам на интернет но неможам да најдам :/
Еве задачи од овој вид.

http://mendo.mk/Task.do?id=704
http://mendo.mk/Task.do?id=629

И исто така задачата од регионалниот натпревар минатата година на која сеуште не го знам одговорот. http://mendo.mk/Task.do?id=614

Вакви задачи се сведуваат на пребарување низ графови и обично се решаваат со BFS (Breadth-First Search) или DFS (Depth-first Search). Сите задачи што ги посочи се решаваат со овој алгоритам, но секако со мали модификации за дадениот проблем.
Задачата Градинар се сведува на откривање на она поле кое може да биде достигнато од најголем број на цвеќиња.
Љубов е многу слична како Градинар, се сведува на наоѓање на ѕидот P за кого збирот од должината на најкраткиот пат од Сашо до P и најкраткиот пат од Елена до P е најголем.
За Чоколадна коцка, проблемот го сведуваме на наоѓање на максималната длабочина на пребарување до која можеме да стигнеме, и колку елементи (коцки) имаме на таа длабочина.

Може некој пример

This message was edited 1 time. Last update was at 23/03/2017 16:54:00

https://www.e-olymp.com/en/problems/1064
https://www.e-olymp.com/en/problems/1060

Еве многу едноставни примери што се решаваат без некои потешкотии. На CodeFu имаш десетици вакви задачи, можеш да ги побараш и таму.

Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.

Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
  
vector< vector<char> > graph;
int maxR = -1, blocks = 0;
map  <pair<int, int>, int> visited, distances, puddles;
int n, m, startX, startY, endX, endY;
queue < pair<int, int> > q, q1;
int di[4] = {-1, 0, 0, 1}, dj[4] = {0, -1, 1, 0};
  
bool isValidPuddle (int pX, int pY){
  
    for (int x = 0; x < 4; x++){
  
            int xCor = pX + di[x] , yCor = pY + dj[x];
  
            if (xCor >= 0 && xCor < n && yCor >= 0 && yCor < m && !visited[make_pair(xCor, yCor)] && graph[xCor][yCor] == '.'){
                return true;
        }
    }
    return false;
}
  
void bfs (int i, int j){
  
    q.push(make_pair(i, j));
    visited[make_pair(i, j)] = 1;
    distances[make_pair(i, j)] = 0;
  
    while(!q.empty()){
  
        pair <int, int> curr = q.front();
        q.pop();
  
        for (int x = 0; x < 4; x++){
  
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x];
  
            if (!visited[make_pair(xCor, yCor)] && xCor >= 0 && xCor < n && yCor >= 0 && yCor < m){
  
                visited[make_pair(xCor, yCor)] = 1;
                distances[make_pair(xCor, yCor)] = distances[curr] + 1;
  
                if (graph[xCor][yCor] == 'E'){
  
                    maxR = distances[make_pair(xCor, yCor)];
                    return;
                }
  
                if (graph[xCor][yCor] == '#' && isValidPuddle(xCor, yCor)){
  
                    puddles[make_pair(xCor, yCor)] = distances[make_pair(xCor, yCor)];
                    visited[make_pair(xCor, yCor)] = 0;
                    blocks++;
                }
  
                if (graph[xCor][yCor] == '.'){
                    q.push(make_pair(xCor, yCor));
                }
            }
        }
    }
    return;
}
  
void bfs2 (int i, int j){
  
     q1.push(make_pair(i, j));
     visited[make_pair(i, j)] = 1;
     distances[make_pair(i, j)] = 0;
  
     while(!q1.empty()){
  
        pair < int, int> curr = q1.front();
        q1.pop();
  
        for (int x = 0 ; x < 4 ; x++){
  
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x]; 
  
            if (!visited[make_pair(xCor, yCor)] && xCor >= 0 && xCor < n  && yCor >= 0 && yCor < m){
  
                visited[make_pair(xCor, yCor)] = 1;
                distances[make_pair(xCor, yCor)] = distances[curr] + 1;
  
                if (puddles[make_pair(xCor, yCor)] != 0){
                    blocks--;
                    maxR = max(maxR, puddles[make_pair(xCor, yCor)] + 1 + distances[curr]);
  
                    if (blocks <= 0){
                        return;
                    }
                }
  
                if (graph[xCor][yCor] == '.'){
                    q1.push(make_pair(xCor, yCor));
                }
  
            }
  
        }
  
     }
     return;
  
} 
  
int main() {
  
    cin >> n >> m;
  
    for (int i = 0 ; i < n; i++){
        graph.push_back(vector<char>());
        for (int j = 0 ; j < m ; j++){
            char val;
            cin >> val;
  
            if (val == 'S'){
                startX = i, startY = j;
            }
  
            if (val == 'E'){
                endX = i, endY = j;
            }
  
            graph[i].push_back(val);
        }
    }
  
    bfs(startX, startY);
  
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
  
    bfs2(endX, endY);
  
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
  
    cout << -1;
  
    return 0;
}

stoki97 wrote: Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.

Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red

Најверојатно користењето на map ти е проблемот. Map структурата во C++ е имплементирана како бинарно пребарувачко дрво, па секое запишување/пребарување го извршува во O(logN) време во најдобар случај. Ако ја смениш map структурата со обична матрица многу ќе ги убрзаш овие операции, односно ќе станат O(1).

Probav so matrica ama na dump pagja neznam zosto eve go kodot.

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
 
struct Node {
 
	Node(char c , bool v, int d){
		val = c;
		visited = v;
		distance = d;
	}
 
	char val;
    bool visited = false; 
    int distance = 0;
}; 
 
vector< vector<Node> > graph;
int maxR = -1, blocks = 0;
 
int n, m, startX, startY, endX, endY;
queue < pair<int, int> > q, q1;
int di[4] = {-1, 0, 0, 1}, dj[4] = {0, -1, 1, 0};
 
bool isValidPuddle (int pX, int pY){
 
    for (int x = 0; x < 4; x++){
 
            int xCor = pX + di[x] , yCor = pY + dj[x];
 
            if (xCor >= 0 && xCor < n && yCor >= 0 && yCor < m && !graph[xCor][yCor].visited && graph[xCor][yCor].val == '.'){
                return true;
        }
    }
    return false;
}
 
void bfs (int i, int j){
 
    q.push(make_pair(i, j));
    graph[i][j].visited = true;
    graph[i][j].distance = 0;
 
    while(!q.empty()){
 
        pair <int, int> curr = q.front();
        q.pop();
 
        for (int x = 0; x < 4; x++){
 
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x];
 
            if (!graph[xCor][yCor].visited && xCor >= 0 && xCor < n && yCor >= 0 && yCor < m){
 
                graph[xCor][yCor].visited = true;
               	graph[xCor][yCor].distance = graph[curr.first][curr.second].distance + 1;
 
                if (graph[xCor][yCor].val == 'E'){
 
                    maxR = graph[xCor][yCor].distance;
                    return;
                }
 
                if (graph[xCor][yCor].val == '#' && isValidPuddle(xCor, yCor)){
                   	graph[xCor][yCor].visited = false;
                    blocks++;
                }
 
                if (graph[xCor][yCor].val == '.'){
                    q.push(make_pair(xCor, yCor));
                }
            }
        }
    }
    return;
}
 
void bfs2 (int i, int j){
 
     q1.push(make_pair(i, j));
     graph[i][j].visited = true;
     graph[i][j].distance = 0;
 
 
     while(!q1.empty()){
 
        pair < int, int> curr = q1.front();
        q1.pop();
 
        for (int x = 0 ; x < 4 ; x++){
 
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x]; 
 
            if (!graph[xCor][yCor].visited && xCor >= 0 && xCor < n  && yCor >= 0 && yCor < m){
 
                graph[xCor][yCor].visited = true;
 
                if (graph[xCor][yCor].distance != 0){
                    blocks--;
                    maxR = max(maxR, graph[xCor][yCor].distance + 1 + graph[curr.first][curr.second].distance);
 
                    if (blocks <= 0){
                        return;
                    }
                }
 
                graph[xCor][yCor].distance = graph[curr.first][curr.second].distance + 1;
 
                if (graph[xCor][yCor].val == '.'){
                    q1.push(make_pair(xCor, yCor));
                }
 
            }
 
        }
 
     }
     return;
 
} 
 
int main() {
 
    cin >> n >> m;
 
    for (int i = 0 ; i < n; i++){
        graph.push_back(vector<Node>());
        for (int j = 0 ; j < m ; j++){
            char val;
            cin >> val;
 
            if (val == 'S'){
                startX = i, startY = j;
            }
 
            if (val == 'E'){
                endX = i, endY = j;
            }
 
            graph[i].push_back(Node(val, false, 0));
        }
    }
 
    bfs(startX, startY);
 
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
 
    bfs2(endX, endY);
 
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
 
    cout << -1;
 
    return 0;
}

This message was edited 1 time. Last update was at 02/04/2017 12:17:43

stoki97 wrote:Probav so matrica ama na dump pagja neznam zosto eve go kodot.

Грешката ти е во оваа линија код:

Проверката дали координатите влегуваат во границите ја правиш откако пробуваш да го прочиташ полето од матрицата, па затоа добиваш и runtime error. Оваа линија се јавува во bfs и во bfs2 процедурата. Стави ги проверките за координатите на почеток и би требало да работи.