Walking Boxes ( 2007 )

Problem :
During the era of DOS games, point-and-click adventure games were able to gain a great deal of popularity before fading away into obscurity, replaced by action games that made use of hardware-accelerated graphics.

In a point-and-click adventure game, the player is able to walk their character around a room by simply clicking where they want to go. One way this is accomplished is through the use of walking boxes. For each room the player explores, in addition to the background image that is visible to the player, there exist a series of connected boxes that the player is constrained to walking within. Keeping the player within these boxes is a straightforward enough task, but navigation from one box to another poses a problem. What if two boxes are not connected directly; which intermediate boxes must his character pass through to arrive at his destination? This problem can be solved through the use of a matrix. To get from one box to another, successive lookups into the matrix will be made until the destination box is reached.

For example, the layout shown above would produce the following matrix:

0 1 1 1 1
0 1 2 3 2
1 1 2 1 4
1 1 1 3 1
2 2 2 2 4

To get from box 0 to box 4, the game engine will look up the element at row 0 and column 4, which is 1, and therefore the character will first proceed to box 1. The lookup for getting from box 1 to box 4 will yield the value 2, so the character will continue to box 2. The next lookup will yield the value 4, which is the number of the destination box, so when the character moves there no further lookups will be required.

Write a program that generates one of these walking box matrices. You will be given a set of boxes and the connections between them. The boxes will never form loops or be isolated from each other, so there will always be exactly one path from one box to another, assuming that paths do not double back on themselves.

Input

Input will consist of a box count on the first line. Whatever this number is, it will be followed by exactly that many additional lines. Each of these lines will specify the other boxes one box is connected to (the first line will be for box 0, the next for box 1, etc.).
Output

Output will consist of the walking boxes matrix that may be used for the purposes of navigation as detailed above. Column and row labels should not be included; only the contents of the matrix are required.

Sample input

5
1
0 2 3
1 4
1
2

Sample output

0 1 1 1 1
0 1 2 3 2
1 1 2 1 4
1 1 1 3 1
2 2 2 2 4

Solution :
Using BFS to generate all paths, then for each position on the matrix, for example m[ i ][ j ] :
we first find generate all paths that we can go from i, then from j we back up the find the second last destination.

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <climits>

using namespace std;

typedef vector< vector< int > > matrix;

vector< string > util_tokenize_string( const string& str, const string& del = " " ) {
    vector< string > result;
    unsigned start = 0;
    unsigned end  = str.find_first_of( del, start );
    unsigned length = str.length();
    string word;

    while( string::npos != end && end < length ) {
        word = str.substr( start, end - start );
        result.push_back( word );
        start = end + 1;
        end = str.find_first_of( del, start );
    }
 
    end = str.find_last_of( del ) + 1;
    result.push_back( str.substr( end ) );
 
    return result;
}
 
int util_string_to_int( const string& s ) {
    istringstream i( s );
    int value;
    i >> value;
    return value;
}
 
template< typename T >
void print_matrix( const vector< vector< T > >& m ) {
    cout << "\n\n";
    int N = m[ 0 ].size();
    for( int i = 0; i < N; ++i ) {
        for( int j = 0; j < N; ++j ) {
            cout <<  "   " << m[ i ][ j ];
        }
        cout << endl << endl;
    }
}
 
vector< vector< bool > > get_list_vertices( const char* file_name ) {
    ifstream inf( file_name );
    int N;
    int count = 0;
    string line;
 
    getline( inf, line );
    N = util_string_to_int( line );
    vector< vector< bool > > m( N, vector< bool >( N, 0 ) );
 
 
    while( getline( inf, line ) ) {
        vector< string > temp = util_tokenize_string( line );
        for( int i = 0; i < temp.size(); ++i ) {
            int to = util_string_to_int( temp[ i ] );
            m[ count ][ to ] = 1;
            m[ to ][ count ] = 1;
        }
        count++;
    }
 
    return m;
}
 
void breadth_first_search( queue< int >& Q,
                           vector< int >& trace,
                           const vector< vector< bool > >& m,
                           int start ) {
    int N = m[ 0 ].size();
    int u;
    Q.push( start );
    trace[ start ] = -INT_MAX;
 
    do {
        u = Q.front();
        Q.pop();
        for( int v = 0; v < N; ++v ) {
            if( ( m[ u ][ v ] == 1 ) && trace[ v ] == -1 ) {
                Q.push( v );
                trace[ v ] = u;
            }
        }
    } while( !Q.empty() );
}
 
int find_trace_path( vector< int > trace, int start, int end, int N ) {
    // direct path
    if( trace[ end ] == start ) {
        return end;
    } else {
        vector< int > v;
        while( end != start ) {
            end = trace[ end ];
            v.push_back( end );
        }
        return v[ v.size() - 2 ];
    }
}
 
int main() {
    int MAXI = 100;
    vector< vector< bool > > m = get_list_vertices( "t.txt" );
    int N = m[ 0 ].size();
    vector< vector< int > > result( N, vector< int >( N, 0 ) );
    for( int i = 0; i < N; ++i ) {
        result[ i ][ i ] = i;
    }
 
    for( int count = 0; count < N; ++count ) {
        queue< int > Q;
        vector< int > trace_path( MAXI, -1 );
        breadth_first_search( Q, trace_path, m, count );
        for( int i = 0; i < N; ++i ) {
            if( count != i )
                result[ count ][ i ] = find_trace_path( trace_path, count, i, N );
        }
    }
 
    print_matrix( result );
 
    return 0;
}