10067

helloneo · Post by **helloneo** » Sat Dec 17, 2005 6:55 pm

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..

please help me.. T.T

Code: Select all

Jan · Post by **Jan** » Mon Dec 26, 2005 1:26 am

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?

helloneo · Post by **helloneo** » Mon Dec 26, 2005 5:22 am

thanks for help..
but my approach was totally wrong..

i never thought about this kind of input..

Code: Select all

liangchene · Post by **liangchene** » Mon Feb 27, 2006 6:00 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;
int answer;
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;
}

answer = 999999999;
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)
{
//we have found our answer
answer= temp.step;
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();
}
}
if (answer == 999999999) cout<<-1<<endl;
else cout<<answer<<endl;

}

system("pause");

return 0;
}

shines · Post by **shines** » Tue Jun 06, 2006 4:58 am

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 · Post by **asif_rahman0** » Sat Jun 24, 2006 5:41 pm

Can someone give me some Input/Output??
I am getting WA.
please help.

Fali · Post by **Fali** » Tue Jun 27, 2006 7:14 am

Hi, I tested my program with a lot of inputs, can you help me !!
If you know a critical input or if you see my mistake, please 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 · Post by **asif_rahman0** » Sun Jul 16, 2006 10:57 pm

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;
		}
		int head=0,cost=0;
		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;}
		while(head<4){
			bool flag1,flag2;
			flag1=flag2=true;
			int c1=0,c2=0,temp=s[head];
			for(i=1;i<=10;i++){
				if(mat[temp][s[1]][s[2]][s[3]]==true&&head==0){
					flag1=false;
					break;
				}
				else if(mat[s[0]][temp][s[2]][s[3]]==true&&head==1){
					flag1=false;
					break;
				}
				else if(mat[s[0]][s[1]][temp][s[3]]==true&&head==2){
					flag1=false;
					break;
				}
				else if(mat[s[0]][s[1]][s[2]][temp]==true&&head==3){
					flag1=false;
					break;
				}
				if(temp==d[head]){
					break;
				}
				else {
					temp=dl[(10+s[head]-i)%10];
					c1++;
				}
			}
			temp=s[head];
			for(i=1;i<=10;i++){
				if(mat[temp][s[1]][s[2]][s[3]]==true&&head==0){
					flag2=false;
					break;
				}
				else if(mat[s[0]][temp][s[2]][s[3]]==true&&head==1){
					flag2=false;
					break;
				}
				else if(mat[s[0]][s[1]][temp][s[3]]==true&&head==2){
					flag2=false;
					break;
				}
				else if(mat[s[0]][s[1]][s[2]][temp]==true&&head==3){
					flag2=false;
					break;
				}
				if(temp==d[head]){
					break;
				}
				else {
					temp=dl[(10+s[head]+i)%10];
					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;
			}
			s[head]=temp;
			head++;
		}
		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;
}

Got 2 Wrong Answer.
Please reply me why getting WA?? Easy BFS. I try to code it like BFS but no hope.

helloneo · Post by **helloneo** » Sat Feb 03, 2007 5:33 pm

Finally got AC..~!
The output for the input above is 4..

sumantbhardvaj · Post by **sumantbhardvaj** » Thu Mar 22, 2007 12:27 am

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 ??

animeshnayan · Post by **animeshnayan** » Mon Apr 16, 2007 10:11 am

I too get TLE using simple BFS...

sumantbhardvaj · Post by **sumantbhardvaj** » Mon Apr 16, 2007 1:51 pm

I have got this problem ac long ago.. just forgot to remove code later..

for BFS , Think abt some pruning

animeshnayan · Post by **animeshnayan** » Tue Apr 17, 2007 8:20 am

I too got ACC

... BFS is enough to get a solution, but how to manage time .. i solve it in 6.6 sec

helloneo · Post by **helloneo** » Tue Apr 17, 2007 12:37 pm

I also solved it with simple BFS.. It runs 0.598 secs..
I used a 4-dimensional array to mark visited states..

cs_lyxaa · Post by **cs_lyxaa** » Thu Oct 04, 2007 4:54 pm

Hey,guys, I still got WA. I need help too...
Any comment is appreciated.

Code: Select all

OJ Board

10067 - Playing with Wheels

10067 - Playing with Wheels

wrong answer!?!?!

10067 - Playing with wheels.. WA