10067 - Playing with Wheels

[Mukit Chowdhury]

Accepted ...

[Mukit Chowdhury]

I missed this case... when source & destination is same & no forbidden configuration is as like as source or destination ...
1
1 1 1 1
1 1 1 1
1
1 2 2 2

[NAbdulla]

getting WA . please help..............

My code:

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <cctype>

using namespace std;

int str2int(char* s)
{
    int k = 0;
    for(int i = 0; s[i] != '\0'; i++){
        if(isdigit(s[i]))k = k*10 + (s[i] - '0');
    }
    return k;
}

int pow10(int n)
{
    int p = 1;
    while(n--){
        p *= 10;
    }
    return p;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int i, j, k, l, n, start, en, test, m, neighbour, pre, mid, post;
    char str[10];

    scanf("%d", &test);
    while(test--){
        getchar();
        gets(str);
        start = str2int(str);

        gets(str);
        en = str2int(str);

        gets(str);
        n = str2int(str);

        int visited[10010] = {0};
        for(i = 0; i < n; i++){//forbidden nodes
            gets(str);
            l = str2int(str);
            visited[l] = 1;
        }

        queue<int>Q;
        Q.push(start);
        int lev[10010];
        lev[start] = 0;
        bool isReach = false;

        if(start == en)printf("0\n");
        else{
            while(!Q.empty() && !isReach){
                int current_node = Q.front();
                Q.pop();
                for(j = 0; j < 4 && !isReach; j++){//four wheels
                    m = pow10(j+1);
                    pre = current_node/m;
                    post = current_node%m;
                    m = pow10(j);
                    mid = post/m;
                    post %= m;
                    for(k = 0; k < 2; k++){
                        int mid1 = mid;
                        if(k){//forward button
                            mid1++;
                            mid1 %= 10;
                        }
                        else{//backward button
                            if(mid1 == 0){
                                mid1 = 9;
                            }
                            else mid1--;
                        }
                        neighbour = (pre*10 + mid1)*pow10(j) + post;

                        if(!visited[neighbour]){
                            visited[neighbour] = 1;
                            lev[neighbour] = lev[current_node] + 1;
                            if(neighbour == en){
                                isReach = true;
                                break;
                            }
                            else Q.push(neighbour);
                        }
                    }
                }
                //cout << Q.size() << endl << endl;
            }
            if(isReach)printf("%d\n", lev[en]);
            else printf("-1\n");
        }
    }
    return 0;
}