UVa : 10067 (Playing with Wheels)


Title : Playing with Wheels

Link : http://uva.onlinejudge.org/external/100/10067.html

Tricky Lines :

  1. if the target configuration is not reachable then print -1.

Analysis :

  1. BFS
    there are at most 10000 possible states.
    0 0 0 0
    0 0 0 1
    0 0 0 2
    .
    .
    .
    9 9 9 9
  2. to move one state to another u don’t need to know which switch actually made the change, but number of times any switch pressed.
  3. From one state u can produce 8 different states. For example
    if initial state : 8 0 5 6
    Child states are :
    8 0 5 7
    8 0 6 6
    8 1 5 6
    9 0 5 6
    8 0 5 5
    8 0 4 6
    8 9 5 6
    7 0 5 6
  4. surely u r not going to visit, already visited states. So u can safely make the forbidden configuration as visited before starting BFS.

Runtime : 3.640s (surprisingly accepted :P)

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int input;
        vector <int> v;
        map <vector <int>, int> pressCnt;
        map <vector <int>, bool> visited;
        queue <vector <int> > q;

        for ( int i = 0; i < 4; i++ ) {
            scanf ("%d", &input);
            v.push_back (input);
        }

        pressCnt [v] = 0;
        q.push (v);

        vector <int> dest;

        for ( int i = 0; i < 4; i++ ) {
            scanf ("%d", &input);
            dest.push_back (input);
        }

        int n;
        scanf ("%d", &n);

        for ( int i = 0; i < n; i++ ) {
            v.clear ();
            for ( int j = 0; j < 4; j++ ) {
                scanf ("%d", &input);
                v.push_back (input);
            }
            visited [v] = true;
        }

        bool resultFound = false;

        while ( !q.empty () ) {
            v.clear ();
            v = q.front ();
            q.pop ();

            if ( visited [v] == true ) continue;

            visited [v] = true;

            if ( v == dest ) {
                resultFound = true;
                break;
            }

            vector <int> child = v;

            for ( int i = 0; i < 4; i++ ) {
                child [i] += 1;
                child [i] %= 10;
                if ( visited [child] == false )
                    q.push (child);
                pressCnt [child] = pressCnt [v] + 1;
                child = v;
            }

            for ( int i = 0; i < 4; i++ ) {
                child [i] -= 1;
                if ( child [i] == -1 ) child [i] = 9;
                if ( visited [child] == false )
                    q.push (child);
                pressCnt [child] = pressCnt [v] + 1;
                child = v;
            }
        }

        if ( resultFound ) printf ("%d\n", pressCnt [dest]);
        else printf ("-1\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Faster Solution : discarding map and vector, using simple integer array

Runtime : 0.172s

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int power (int b, int p)
{
    if ( p == 4 ) return 10000;
    if ( p == 3 ) return 1000;
    if ( p == 2 ) return 100;
    if ( p == 1 ) return 10;
    return 1;
}

int make_number (int c [])
{
    int ret = 0;

    ret += c [0] * 1000;
    ret += c [1] * 100;
    ret += c [2] * 10;
    ret += c [3];

    return ret;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int input;
        int pressCnt [10000 + 10];
        bool visited [10000 + 10];
        queue <int> q;

        memset (pressCnt, 0, sizeof (pressCnt));
        memset (visited, 0, sizeof (visited));

        int number = 0;
        for ( int i = 0; i < 4; i++ ) {
            scanf ("%d", &input);
            number += (input * power (10, 3 - i));
        }

        pressCnt [number] = 0;
        q.push (number);

        int destination = 0;

        for ( int i = 0; i < 4; i++ ) {
            scanf ("%d", &input);
            destination += (input * power (10, 3 - i));
        }

        int n;
        scanf ("%d", &n);

        for ( int i = 0; i < n; i++ ) {
            number = 0;
            for ( int j = 0; j < 4; j++ ) {
                scanf ("%d", &input);
                number += (input * power (10, 3 - j));
            }
            visited [number] = true;
        }

        bool resultFound = false;

        while ( !q.empty () ) {
            number = q.front ();
            q.pop ();

            if ( visited [number] == true ) continue;

            visited [number] = true;

            if ( number == destination ) {
                resultFound = true;
                break;
            }

            int child [4];
            child [3] = number % 10;
            child [2] = (number % 100) / 10;
            child [1] = (number % 1000) / 100;
            child [0] = number / 1000;

            for ( int i = 0; i < 4; i++ ) {
                child [i] += 1;
                child [i] %= 10;
                int num = make_number (child);
                if ( visited [num] == false )
                    q.push (num);
                pressCnt [num] = pressCnt [number] + 1;

                child [3] = number % 10;
                child [2] = (number % 100) / 10;
                child [1] = (number % 1000) / 100;
                child [0] = number / 1000;
            }

            for ( int i = 0; i < 4; i++ ) {
                child [i] -= 1;
                if ( child [i] == -1 ) child [i] = 9;
                int num = make_number (child);
                if ( visited [num] == false )
                    q.push (num);
                pressCnt [num] = pressCnt [number] + 1;

                child [3] = number % 10;
                child [2] = (number % 100) / 10;
                child [1] = (number % 1000) / 100;
                child [0] = number / 1000;
            }
        }

        if ( resultFound ) printf ("%d\n", pressCnt [destination]);
        else printf ("-1\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s