AP2 2018-05-09

1a-P56483-dfs-rec.cc

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


using Graf = vector<vector<int>>; // llistes d'adjacència


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


int main() {
    int n, m;
    cin >> n >> m;
    
    Graf 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 Graf = vector<vector<int>>; // llistes d'adjacència


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


int main() {
    int n, m;
    cin >> n >> m;
    
    Graf 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 Graf = vector<vector<int>>; // llistes d'adjacència


// Nota: EN un BFS no es fa servir vis síno encuat. Però aquí veníem del def-ite i ha quedat així.

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


int main() {
    int n, m;
    cin >> n >> m;
    
    Graf 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 <map>
using namespace std;


using Graf = vector<vector<int>>; // llistes d'adjacència


void dfs(const Graf& G, int u, int y, vector<bool>& vis) {
    if (not vis[u]) {
        // fer algunac osa amb u
        vis[u] = true;
        if (vis[y]) return;
        for (int v : G[u]) {
            dfs(G, v, y, vis);
        }
    }
}


int main() {
    int n;
    cin >> n;
    
    map<string, int> ids;
    for (int i = 0; i < n; ++i) {
        string nom;
        cin >> nom;
        ids[nom] = i;
    }
    
    int m;
    cin >> m;
    Graf G(n);
    for (int i = 0; i < m; ++i) {
        string nomu, nomv;
        cin >> nomu >> nomv;
        int u = ids[nomu];
        int v = ids[nomv];
        G[u].push_back(v);
    }
    
    string nomx, nomy;
    cin >> nomx >> nomy;
    int x = ids[nomx];
    int y = ids[nomy];
    
    vector<bool> vis(n, false);
    dfs(G, x, y, vis);
    if (vis[y]) cout << "yes" << endl; 
    else cout << "no" << endl;
}

3-P38753.cc

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


using MatriuC = vector<vector<char>>;
using MatriuB = vector<vector<bool>>;


bool es_pot_anar(int x, int y, const Matriu& M) {
    int n = M.size();
    int m = M[0].size();
    return x >= 0 and y >= 0 and x < n and y < m and M[x][y] != 'X';
}


void dfs(const Matriu& M, int x, int y, MatriuB& vis, bool& trobat) {
    if (not trobat and not vis[x][y]) {
        if (M[x][y] == 't') {
            trobat = true;
        } else {
            vis[x][y] = true;
            // Nota: hagués quedat millor una funció que mira si es pot anar i, en cas afirmatiu, crida dfs directament.
            if (es_pot_anar(x+1, y, M)) dfs(M, x+1, y, vis, trobat);
            if (es_pot_anar(x-1, y, M)) dfs(M, x-1, y, vis, trobat);
            if (es_pot_anar(x, y+1, M)) dfs(M, x, y+1, vis, trobat);
            if (es_pot_anar(x, y-1, M)) dfs(M, x, y-1, vis, trobat);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    Matriu M(n, vector<char>(m));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> M[i][j];
        }
    }
    
    int ox, oy;
    cin >> ox >> oy;
    --ox; --oy;
    
    MatriuB vis(n, vector<bool>(m, false));
    
    bool trobat = false;
    dfs(M, ox, oy, vis, trobat);
    
    if (trobat) cout << "yes" << endl;
    else cout << "no" << endl;
}