dimanche 29 mai 2016

What's wrong about this algorithm for solving "Help the Commander in Chief"

Well, I searched trying to find an answer for this problem : http://ift.tt/1wqje1m Actually I found some of them, but I'm still curious about this one which is wrong, Here's the code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

using size_type = unsigned long long int;
using ushort = unsigned short;

class Node
{
public :
    void addEdge(ushort e) {_edges.push_back(e);}
    const ushort &operator[] (int n) const {return _edges[n];}
    ushort size() const {return _edges.size();}
    void clear() {_edges.clear();}
private :
    vector<ushort> _edges;
};

class Map
{
public :
    Map() : _C{0}, _B{0}, _S{0}, _T{0} {}

    Node& operator[] (const ushort i) {return _Node[i];}
    const Node& operator[] (const ushort i) const {return _Node[i];}

    friend istream &operator>> (istream &is, Map &m);

    ushort C() {return _C;}
    ushort B() {return _B;}
    ushort start() {return _S;}
    ushort end() {return _T;}
private :
    void _reset();
    Node _Node[10000];
    ushort _C, _B, _S, _T;
};

void Map::_reset()
{
    for (ushort i = 0; i < _C; i++)
        _Node[i].clear();
}

istream &operator>>(istream &is, Map &m)
{
    m._reset();
    ushort x, y;
    scanf("%hu %hu %hu %hu", &m._C, &m._B, &m._S, &m._T);
    m._S--; m._T--;
    for (ushort i = 0; i < m._B; i++)
    {
        scanf("%hu %hu", &x, &y);
        x--; y--;
        m[x].addEdge(y);
    }
    return is;
}

size_type paths(Map &m);
void count(Map &m, ushort p, map<ushort, size_type> &h);

int main()
{
    Map m;
    ushort D;
    scanf("%hu", &D);
    while (D--)
    {
        cin >> m;
        printf("%I64u\n", paths(m) % 1000000007LL);
    }
}

size_type paths(Map &m)
{
    if (m.start() == m.end()) return 1;
    map<ushort, size_type> h;
    h[m.end()] = 1;
    count(m, m.start(), h);
    return h[m.start()];
}

void count(Map &m, ushort p, map<ushort, size_type> &h)
{
    for (ushort i = 0; i < m[p].size(); i++)
    {
        if (h.find(m[p][i]) == h.end())
            count(m, m[p][i], h);
        h[p] += h[m[p][i]];
    }
}

I simply try to use memorization to count number of paths, but wherever I go, they talk about topological sort.. etc. why this code fragment is still giving a wrong answer ? why is it not sufficient ?

Thanks - Sam

Aucun commentaire:

Enregistrer un commentaire