10067 - Playing with Wheels

[Jan]

Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2

Output:

Code: Select all

11
14

Hope these help.

[cs_lyxaa]

Thanks so much. I finally got AC in 0.67s!!~~~
Through your case, I found that the bug was the negative modular arithmetic. C++ gives me the result that (-1)%10=-1. No wonder I got WA before.

Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2

Output:

Code: Select all

11
14

Hope these help.

[Jan]

You are welcome. Remove your old code please.

[Zyaad Jaunnoo]

I am getting wrong answer

I tried the test cases posted and I am getting the correct answer.

Any other tricky test cases?

Will appreciate your help.

[Jan]

I think many tricky cases are posted already. You can post your code, cause then it would be easier to check..

[Zyaad Jaunnoo]

Below is my code...

Code: Select all

#include <iostream>
#include <list>

using namespace std;

#define TRUE    1
#define FALSE   0
#define LEFT    0
#define RIGHT   1

int N;
int S1, S2, S3, S4, S;
int T1, T2, T3, T4, T;
int F1, F2, F3, F4, F;
int forbidden [10000];
int g[10000][8];
int steps[10000];


void cleanUp() {
    for (int i = 0; i < 10000; i++) {
        forbidden[i] = FALSE;
        steps[i] = -1;
    }
}

int nextConfig (int state, int button, int direction) {
    int digit, order, toAdd;

    if (button == 1) order = 1000;
    else if (button == 2) order = 100;
    else if (button == 3) order = 10;
    else if (button == 4) order = 1;

    digit = (state % (order * 10)) / order;

    if (direction == RIGHT) {
        toAdd = -1 * order;
        if (digit == 0) toAdd = 9 * order;
    }
    else {
        toAdd = 1 * order;
        if (digit == 9) toAdd = -9 * order;
    }

    return (state + toAdd);
}


void buildGraph() {
    for (int i = 0; i < 10000; i++) {
        g[i][0] = nextConfig(i, 1, LEFT);
        g[i][1] = nextConfig(i, 1, RIGHT);

        g[i][2] = nextConfig(i, 2, LEFT);
        g[i][3] = nextConfig(i, 2, RIGHT);

        g[i][4] = nextConfig(i, 3, LEFT);
        g[i][5] = nextConfig(i, 3, RIGHT);

        g[i][6] = nextConfig(i, 4, LEFT);
        g[i][7] = nextConfig(i, 4, RIGHT);
    }
}


void readData() {
    cin >> S1 >> S2 >> S3 >> S4;
    S = (S1 * 1000) + (S2 * 100) + (S3 * 10) + S4;

    cin >> T1 >> T2 >> T3 >> T4;
    T = (T1 * 1000) + (T2 * 100) + (T3 * 10) + T4;

    int n;  //  no of forbidden configurations

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> F1 >> F2 >> F3 >> F4;
        F = (F1 * 1000) + (F2 * 100) + (F3 * 10) + F4;
        forbidden[F] = TRUE;
    }
}

int traverseG() {
    list <int> L;   //  queue to hold configurations
    list <int> :: iterator i;
    int currentConfig, neighbour;

    if (forbidden[T] || forbidden[S]) return -1;
    if (S == T) return 0;

    L.push_back(S);
    steps[S] = 0;

    for (i = L.begin(); L.size() > 0; i++) {
        currentConfig = *i;
        L.pop_front();

        for (int j = 0; j < 8; j++) {
            neighbour = g[currentConfig][j];
            //if (neighbour == T)
            //    return steps[currentConfig] + 1;

            if (!forbidden [neighbour] && steps[neighbour] == -1) {
                steps[neighbour] = steps[currentConfig] + 1;
                if (neighbour == T) return steps[neighbour];

                L.push_back(neighbour);
            }
        }
    }

    //  not found
    return -1;
}


int main() {
    cin >> N;

    buildGraph();

    for (int i = 0; i < N; i++) {
        cleanUp();
        readData();
        cout << traverseG() << endl;
    }


    return 0;
}


[Jan]

Your code looks correct to me. But one question. You are using list. Is there any problem using stl queue?

[Zyaad Jaunnoo]

I haven't tried yet.

Will try and let you know..

Thanks for the help.

[barry800414]

Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2

Output:

Code: Select all

11


14

Hope these help.

Thanks for your test data!

[ary]

i got wa.. i dunt know whats wrong.. already consider forbidden equal to target, and everything.. plz help me geniuses.. @_@

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cmath>
//#include <conio.h>
using namespace std;
typedef struct {
int f[4];
} forbidden;

bool cg[4];
int cur[4];
int target[4];
int counter;
bool cant,ok;
vector<forbidden> forbid,candi,visited;
forbidden forb;

bool compara(int a[], int b[]){

for(int i=0;i<4;i++){
if(a[i] != b[i]){
return false;
}
}
return true;
}

int calc(int a[],int b[]){
int sum=0,d,e;
for(int i=0;i<4;i++){
d = abs(a[i]-b[i]);
if(d>5){
if(a[i]<b[i]){
sum += a[i] + (9-b[i])+1;
}else{
sum += b[i] + (9-a[i]) +1;
}
}else
sum += d;
}
return sum;
}

void choose(int a[]){
int p[9][4];
int max=0,temp,n;

p[3][0] = p[4][0] = p[5][0] = p[6][0] = p[7][0] = p[8][0] = a[0];
if(a[0]==9)
p[1][0] = 0;
else
p[1][0] = a[0] +1;
if(a[0]==0)
p[2][0] = 9;
else
p[2][0] = a[0] -1;

p[1][1] = p[2][1] = p[5][1] = p[6][1] = p[7][1] = p[8][1] = a[1];
if(a[1]==9)
p[3][1] = 0;
else
p[3][1] = a[1] +1;
if(a[1]==0)
p[4][1] = 9;
else
p[4][1] = a[1] -1;

p[3][2] = p[4][2] = p[1][2] = p[2][2] = p[7][2] = p[8][2] = a[2];
if(a[2] == 9)
p[5][2] = 0;
else
p[5][2] = a[2] +1;
if(a[2] == 0)
p[6][2] = 9;
else
p[6][2] = a[2] -1;

p[3][3] = p[4][3] = p[5][3] = p[6][3] = p[1][3] = p[2][3] = a[3];
if(a[3]==9)
p[7][3] = 0;
else
p[7][3] = a[3] +1;
if(a[3] ==0)
p[8][3] = 9;
else
p[8][3] = a[3] -1;

for(int i=1;i<9;i++){
for(int c=0;c<4;c++){
forb.f[c] = p[i][c];
}
candi.push_back(forb);
}

for(int z=0;z<forbid.size();z++){
for(int i=0;i<candi.size();i++){
ok = false;
for(int c=0;c<4;c++){
if(candi[i].f[c] != forbid[z].f[c])
ok=true;
}
if(!ok)
candi.erase(candi.begin()+i);
}
}

for(int z=0;z<visited.size();z++){
for(int i=0;i<candi.size();i++){
ok = false;
for(int c=0;c<4;c++){
if(candi[i].f[c] != visited[z].f[c])
ok=true;
}
if(!ok)
candi.erase(candi.begin()+i);
}
}

/*
for(int i=0;i<candi.size();i++){
for(int c=0;c<4;c++){
cout<<candi[i].f[c];
}
cout<<endl;
}
*/
if(!candi.empty()) {
max = calc(candi[0].f,target);
n=0;
for(int i=1;i<candi.size();i++){
temp = calc(candi[i].f,target);
if(temp<max){
max = temp;
n=i;
}
}
//cout<<"1"<<endl;
/*
for(int c=0;c<4;c++){
cout<<candi[n].f[c];
}
cout<<endl;
*/
for(int c=0;c<4;c++){
cur[c] = candi[n].f[c];
}
counter++;
}
else {
cant = true;
}

}


int main(){
freopen("10067.txt","r",stdin);
freopen("10067O.txt","w",stdout);
bool notre;
int current,targe,fn,ff,T;

cin>>T;

for(int z=0;z<T;z++){

cin>>cur[0];
cin>>cur[1];
cin>>cur[2];
cin>>cur[3];

cin>>target[0];
cin>>target[1];
cin>>target[2];
cin>>target[3];

cin>>fn;

for(int i=0;i<fn;i++){
cin>>forb.f[0];
cin>>forb.f[1];
cin>>forb.f[2];
cin>>forb.f[3];

forbid.push_back(forb);
}

cant = false;
counter = 0;
//cout<<calc(cur,target)<<endl;

for(int z=0;z<forbid.size();z++){
ok = false;
for(int c=0;c<4;c++){
if(target[c] != forbid[z].f[c])
ok=true;
}
if(!ok)
cant = true;
}

while(!compara(cur,target) && !cant){
choose(cur);
for(int i=0;i<4;i++){
forb.f[i] = cur[i];
}
visited.push_back(forb);
}
if(cant)
cout<<"-1"<<endl;
else
cout<<counter<<endl;

// getch();
forbid.clear();
candi.clear();
visited.clear();
}
//getch();
return 0;
}

[Articuno]

Problem fixed....

Code: Select all

AC


[Articuno]

There is a test case where the starting sequence is in the forbidden list. I got some WA for that reason. Try out this input:

Code: Select all

1
8 0 5 6
6 5 0 8
1
8 0 5 6


Output:

Code: Select all

-1


[erkape]

still got a WA, i already checked all test cases in the post and it was right.. but still WA..
is there any other special test case?

[Shafaet_du]

bfs

[Monty]

Tried every test case in this thread and I pass all of them, still I keep getting WA.. Not sure what else to do, I made sure I handled cases where the start is the target, the target is in the forbidden list, 9+1 goes to 0, 0-1 goes to 9. Are there any other elementary cases I could be tripping up on? Thanks


10 Cases:

Code: Select all

10
9 9 9 9
9 9 9 9
1
9 9 9 9

9 9 9 9
0 0 0 0
1
0 0 0 0

9 9 9 9
0 0 0 0
1
9 9 9 9

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

9 9 9 9
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

9 9 9 9
0 0 1 1
3
8 9 0 7
6 5 4 2
2 3 4 5

0 0 0 0
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
6 5 7 9
8 5 7 9

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
0 0 0 0
8 5 7 9

1 7 1 0
7 0 0 0
6
1 9 0 7
1 4 2 2
1 3 4 5
4 4 4 4
2 5 0 9
1 1 7 9



My Output:

Code: Select all

0
-1
4
10
5
6
1
11
11
8