## 10067 - Playing with Wheels

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10067 - Playing with Wheels

I think I take care every case.. but WA.. is there any special case..? or anything wrong with my code..?
I use "next_permutation" to generate every sequence of wheels to adjust .. and backtracking.. but WA..

Last edited by helloneo on Thu Oct 04, 2007 8:45 am, edited 3 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Suppose the initial position is 0 0 9 9. You can go to...

Code: Select all

``````1 0 9 9,
9 0 9 9,
0 1 9 9,
0 9 9 9,
.........``````
Did you consider this?
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
thanks for help..
but my approach was totally wrong..

Code: Select all

``````1
0 0 9 9
2 0 9 9
2
1 0 9 9
9 0 9 9
``````

liangchene
New poster
Posts: 12
Joined: Thu May 19, 2005 6:07 am

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<deque>

using namespace std;

ifstream filein ("test.in");

int N;

int n;

struct set
{
int a,b,c,d,step;
};

bool equal (set a, set b)
{
if (a.a!=b.a) return false;
if (a.b!=b.b) return false;
if (a.c!=b.c) return false;
if (a.d!=b.d) return false;

return true;
}

int up(int num)
{
num++;
if (num==10) return 0;
return num;
}

int down(int num)
{
num--;
if (num==-1) return 9;
return num;
}

deque<set> que1;

int small [10][10][10][10];
bool valid[10][10][10][10];
int main()
{
//first of all, generate fibonacci numbers
int x,y,w;
set dummy;
set start;
set end;

filein>>N;
int a,b,c,d;
set temp;

for (w=0;w<N;w++)
{
for (a=0;a<10;a++)
for (b=0;b<10;b++)
for (c=0;c<10;c++)
for (d=0;d<10;d++)
{
small[a][c][d]=999999999;
valid[a][c][d]=true;
}

que1.clear();
//start
filein>>start.a>>start.b>>start.c>>start.d;

small[start.a][start.b][start.c][start.d]=3;
//end
filein>>end.a>>end.b>>end.c>>end.d;

filein>>n;
for (x=0;x<n;x++)
{
filein>>a>>b>>c>>d;
valid[a][c][d]=false;
}

//do a bfs
dummy= start;
dummy.step=0;
que1.push_back(dummy);

if (valid[start.a][start.b][start.c][start.d]==false || valid[end.a][end.b][end.c][end.d]==false)
{
}
else
{
while(!que1.empty())
{
temp= que1[0];

if (equal(temp,end) && temp.step!=0)
{
break;
}
if (valid[up(temp.a)][temp.b][temp.c][temp.d] && temp.step+1<small[up(temp.a)][temp.b][temp.c][temp.d])
{
small[up(temp.a)][temp.b][temp.c][temp.d]=temp.step+1;
temp.step ++;
temp.a = up(temp.a);
que1.push_back(temp);
temp=que1[0];
}

if (valid[down(temp.a)][temp.b][temp.c][temp.d] && temp.step+1<small[down(temp.a)][temp.b][temp.c][temp.d])
{
small[down(temp.a)][temp.b][temp.c][temp.d]=temp.step+1;
temp.step ++;
temp.a = down(temp.a);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][up(temp.b)][temp.c][temp.d] && temp.step+1<small[temp.a][up(temp.b)][temp.c][temp.d])
{
small[temp.a][up(temp.b)][temp.c][temp.d]= temp.step+1;
temp.step ++;
temp.b = up(temp.b);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][down(temp.b)][temp.c][temp.d] && temp.step+1<small[temp.a][down(temp.b)][temp.c][temp.d])
{
small[temp.a][down(temp.b)][temp.c][temp.d]= temp.step+1;
temp.step ++;
temp.b = down(temp.b);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][temp.b][up(temp.c)][temp.d] && temp.step+1<small[temp.a][temp.b][up(temp.c)][temp.d])
{
small[temp.a][temp.b][up(temp.c)][temp.d]= temp.step+1;
temp.step ++;
temp.c = up(temp.c);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][temp.b][down(temp.c)][temp.d] && temp.step+1<small[temp.a][temp.b][down(temp.c)][temp.d])
{
small[temp.a][temp.b][down(temp.c)][temp.d]= temp.step+1;
temp.step ++;
temp.c = down(temp.c);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][temp.b][temp.c][up(temp.d)] && temp.step+1<small[temp.a][temp.b][down(temp.c)][up(temp.d)])
{
small[temp.a][temp.b][temp.c][up(temp.d)]= temp.step+1;
temp.step ++;
temp.d = up(temp.d);
que1.push_back(temp);
temp=que1[0];
}

if (valid[temp.a][temp.b][temp.c][down(temp.d)] && temp.step+1<small[temp.a][temp.b][down(temp.c)][down(temp.d)])
{
small[temp.a][temp.b][temp.c][down(temp.d)]= temp.step+1;
temp.step ++;
temp.d = down(temp.d);
que1.push_back(temp);
temp=que1[0];
}

que1.pop_front();
}
}

}

system("pause");

return 0;
}

shines
New poster
Posts: 4
Joined: Fri Apr 07, 2006 1:58 pm
helloneo wrote:

Code: Select all

``````1
0 0 9 9
2 0 9 9
2
1 0 9 9
9 0 9 9
``````
my answer is 4 in this case. Is it right?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
Can someone give me some Input/Output??
I am getting WA.

Fali
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

### 10067 - Playing with wheels.. WA

Hi, I tested my program with a lot of inputs, can you help me !!

Code: Select all

``````/*
Playing with wheels, Uva # 10067
Nephtali Garrido
24/06/06
*/
#include <cstdio>
using namespace std;
struct conf
{      bool disp;
int d;
}v[10000];

int m,n,a,b,c,d,i,o,col[10000],cab,rab,c2,ii;

int main()
{   scanf("%d",&m);
while(m>0)
{ scanf("%d %d %d %d",&a,&b,&c,&d);
i=d+(c*10)+(b*100)+(a*1000);
scanf("%d %d %d %d",&a,&b,&c,&d);
o=d+(c*10)+(b*100)+(a*1000);
scanf("%d",&n);
for(c2=0;c2<10000;c2++)
v[c2].disp=true;
for(c2=0;c2<n;c2++)
{ scanf("%d %d %d %d",&a,&b,&c,&d);
ii=d+(c*10)+(b*100)+(a*1000);
v[ii].disp=false;
v[ii].d=-1;
}
if(v[i].d==-1 || v[o].disp==false)
printf("-1\n");
else if(i==o)
printf("0\n");
else
{v[i].disp=false;
v[i].d=0;
cab=0;
rab=-1;
col[cab]=i;
while(rab!=cab)
{ rab++;
if(rab==10000)
rab=0;
c2=i=col[rab];
d=v[i].d;
d++;
if(i%10==0)
i+=9;
else
i--;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if(i%10==9)
i-=9;
else
i++;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/10)%10==0)
i+=90;
else
i-=10;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/10)%10==9)
i-=90;
else
i+=10;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/100)%10==0)
i+=900;
else
i-=100;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/100)%10==9)
i-=900;
else
i+=100;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/1000)%10==0)
i+=9000;
else
i-=1000;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
i=c2;
if((i/1000)%10==9)
i-=9000;
else
i+=1000;
if(i==o)
break;
else if(v[i].disp==true)
{ cab++;
if(cab==10000)
cab=0;
col[cab]=i;
v[i].disp=false;
v[i].d=d;
}
}
if(rab==cab)
printf("-1\n");
else
printf("%d\n",d);
}
m--;
}
return 0;
}

``````

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10067

Here is my code :

Code: Select all

``````#include <cstdio>
#include <cstring>
bool mat[12][12][12][12];
int dl[10]={0,1,2,3,4,5,6,7,8,9};
int s[15];
int d[15];
int main()
{
int tst,i,fb;
int a,b,c,dd;
scanf("%d",&tst);
while(tst--){
memset(mat,false,sizeof(mat));memset(mat,false,sizeof(s));memset(mat,false,sizeof(d));
for(i=0;i<1;i++) {
scanf("%d%d%d%d",&s[0],&s[1],&s[2],&s[3]);
scanf("%d%d%d%d",&d[0],&d[1],&d[2],&d[3]);
}
scanf("%d",&fb);
for(i=0;i<fb;i++){
scanf("%d%d%d%d",&a,&b,&c,&dd);
mat[a][b][c][dd]=true;
}
if(mat[s[0]][s[1]][s[2]][s[3]]==true){printf("-1\n");continue;}
if(mat[d[0]][d[1]][d[2]][d[3]]==true){printf("-1\n");continue;}
bool flag1,flag2;
flag1=flag2=true;
for(i=1;i<=10;i++){
flag1=false;
break;
}
flag1=false;
break;
}
flag1=false;
break;
}
flag1=false;
break;
}
break;
}
else {
c1++;
}
}
for(i=1;i<=10;i++){
flag2=false;
break;
}
flag2=false;
break;
}
flag2=false;
break;
}
flag2=false;
break;
}
break;
}
else {
c2++;
}
}
if(flag1==false&&flag2==false) break;
if(flag1==false&&flag2==true) cost+=c2;
else if(flag1==true&&flag2==false) cost+=c1;
else {
if(c1<c2) cost+=c1;
else if(c1==c2) cost+=c2;
else cost+=c2;
}
}
if(s[0]==d[0]&&s[1]==d[1]&&s[2]==d[2]&&s[3]==d[3]) printf("%d\n",cost);
else printf("-1\n");
}
return 0;
}
``````
Please reply me why getting WA?? Easy BFS. I try to code it like BFS but no hope.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Finally got AC..~!
The output for the input above is 4..
Last edited by helloneo on Mon Apr 16, 2007 6:12 pm, edited 1 time in total.

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:
why i m keep on getting TLE in this problem. I hv applied simple BFS.

Code: Select all

`````` ACC :)

``````
How can i make this algo efficient ??
Last edited by sumantbhardvaj on Mon Apr 16, 2007 1:52 pm, edited 1 time in total.

animeshnayan
New poster
Posts: 5
Joined: Tue Mar 20, 2007 7:44 am
I too get TLE using simple BFS...
I am striving to write bug free codes (

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:
I have got this problem ac long ago.. just forgot to remove code later..

for BFS , Think abt some pruning

animeshnayan
New poster
Posts: 5
Joined: Tue Mar 20, 2007 7:44 am
I too got ACC ... BFS is enough to get a solution, but how to manage time .. i solve it in 6.6 sec
I am striving to write bug free codes (

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
I also solved it with simple BFS.. It runs 0.598 secs..
I used a 4-dimensional array to mark visited states..

cs_lyxaa
New poster
Posts: 3
Joined: Thu Oct 04, 2007 6:50 am
Hey,guys, I still got WA. I need help too...
Any comment is appreciated.
Last edited by cs_lyxaa on Mon Oct 08, 2007 11:56 am, edited 1 time in total.