AP2 2018-05-10

1a-P56483-dfs-rec.cc

#include <iostream>
#include <vector>
using namespace std;


using Graph = vector<vector<int>>;


void dfs (const Graph& G, int u, int y, vector<bool>& vis) {
    vis[u] = true;
    for (int v : G[u]) {
        if (not vis[v] and not vis[y]) dfs(G, v, vis);
    }
}


int main() {
    int n, m;
    cin >> n >> m;

    Graph G(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    int x, y;
    cin >> x >> y;

    vector<bool> vis(n, false);
    dfs(G, x, y, vis);

    if (vis[y]) cout << "yes" << endl;
    else cout << "no" << endl;
}

1b-P56483-dfs-ite.cc

#include <iostream>
#include <vector>
#include <stack>
using namespace std;


using Graph = vector<vector<int>>;


void dfs (const Graph& G, int x, int y, vector<bool>& enc) {
    stack<int> p;
    p.push(x);
    while (not p.empty()) {
        int u = p.front();
        p.pop();
        vis[u] = true;
        if (u == y) return;
        for (int v : G[u]) {
            if (not vis[v]) {
                p.push(v);
            }
        }
    }
}


int main() {
    int n, m;
    cin >> n >> m;

    Graph G(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    int x, y;
    cin >> x >> y;

    vector<bool> vis(n, false);
    dfs(G, x, y, vis);

    if (vis[y]) cout << "yes" << endl;
    else cout << "no" << endl;
}

1c-P56483-bfs.cc

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


using Graph = vector<vector<int>>;


void bfs (const Graph& G, int x, int y, vector<bool>& enc) {
    queue<int> q;
    q.push(x);
    enc[x] = true;
    if (x == y) return;
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (not enc[v]) {
                q.push(v);
                enc[v] = true;
                if (v == y) return;
}   }   }   }            


int main() {
    int n, m;
    cin >> n >> m;

    Graph G(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    int x, y;
    cin >> x >> y;

    vector<bool> vis(n, false);
    bfs(G, x, y, vis);

    if (vis[y]) cout << "yes" << endl;
    else cout << "no" << endl;
}

2-P37001.cc

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;


using Graph = vector<vector<int>>;


void bfs (const Graph& G, int x, int y, vector<bool>& enc) {
    queue<int> q;
    q.push(x);
    enc[x] = true;
    if (x == y) return;
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (not enc[v]) {
                q.push(v);
                enc[v] = true;
                if (v == y) return;
}   }   }   }


int main() {
    int n;
    cin >> n;

    map<string, int> ids;
    for (int u = 0; u < n; ++u) {
        string s;
        cin >> s;
        ids[s] = u;
    }

    Graph G(n);

    int m;
    cin >> m;

    for (int i = 0; i < m; ++i) {
        string su, sv;
        cin >> su >> sv;
        int u = ids[su];
        int v = ids[sv];
        G[u].push_back(v);
    }

    string sx, sy;
    cin >> sx >> sy;
    int x = ids[sx];
    int y = ids[sy];

    vector<bool> vis(n, false);
    bfs(G, x, y, vis);

    if (vis[y]) cout << "yes" << endl;
    else cout << "no" << endl;
}

3-P38753.cc

#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;


using MatriuC = vector<vector<char>>;
using MatriuB = vector<vector<bool>>;
using intint = pair<int, int>;


void tractar (int x, int y, const MatriuC& M, MatriuB& vis, stack<intint>& p) {
    int n = M.size();
    int m = M[0].size();
    if (x >=0 and y >= 0 and x < n and y < m and M[x][y] != 'X' and not vis[x][y]) {
        p.push({x, y});
}   }


bool dfs (const MatriuC& M, int px, int py, MatriuB& vis) {
    stack<intint> p;
    p.push({px, py});
    while (not p.empty()) {
        intint par = p.top();
        p.pop();
        int x = par.first;
        int y = par.second;
        if (M[x][y] == 't') return true;
        if (not vis[x][y]) {
            vis[x][y] = true;
            tractar(x+1, y, M, vis, p);
            tractar(x-1, y, M, vis, p);
            tractar(x, y+1, M, vis, p);
            tractar(x, y-1, M, vis, p);
    }   }    
    return false;
}


int main() {
    int n, m;
    cin >> n >> m;

    MatriuC M(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> M[i][j];
    }   }    

    int px, py;
    cin >> px >> py;
    --px; --py;

    MatriuB vis(n, vector<bool>(m, false));
    bool trobat = dfs(M, px, py, vis);

    if (trobat) cout << "yes" << endl;
    else cout << "no" << endl;
}

Les tres últimes línies de cod, del 3-P38753.cc, seria més pràctic/eficient no declarar una variable booleana, i utilitzar en comptes un ternari?
cout << (dfs(M,px,py,vis)? "yes" : "no") << endl;

Sí: Seria totalment equivalent i igual d'eficient.

Bon dia.
A l'últim snippet, l'algoritme de recorregut no hauria de dir-se BFS?

Merci.