DIGJUMP WA Implemented as per editorial.

general
1

//http://www.codechef.com/viewsolution/4080130

I have made correct implementation as per the solution provided above, taking care of all corner cases. But it still gives me WA. Please help.

include

include

include

include

include

using namespace std; int main()

{

int i,j,top,len=0,cnt=0;

int pos[100005];

string s;

int a[10];

for(i=0;i<10;a[i++]=0);

cin>>s;

i=0;

while(i<s.size())
{
pos[i]=s[i]-‘0’;
i++;
a[s[i]-‘0’]++;
}
cnt=s.size();
int**v=(int *)calloc(10,sizeof(int));
for(i=0;i<10;i++)
v[i]=(int *)calloc(a[i],sizeof(int));
for(i=0;i<10;i++)
{
len=0;
for(j=0;j<cnt;j++)
if(pos[j]==i)
v[i][len++]=j;
}
int prev[cnt];
for(i=0;i<cnt;i++)
prev[i]=-1;
queuebfs;
prev[0]=-2;
bfs.push(0);
len=cnt;
while(!bfs.empty())
{
top=bfs.front();
if(top==len-1)
break;
bfs.pop();
i=0;
while(i<a[pos[top]])
{
if(prev[v[pos[top]][i]]==-1)
{
prev[v[pos[top]][i]]=top;
bfs.push(v[pos[top]][i]);

    }
    i++;
}
a[pos[top]]=0;
if(top==0)
{
    if(prev[top+1]==-1)
    {
        bfs.push(top+1);
        prev[top+1]=top;
    }
}
else
{
    if(prev[top-1]==-1)
    {
        bfs.push(top-1);
        prev[top-1]=top;
    }

    if(prev[top+1]==-1)
    {
        bfs.push(top+1);
        prev[top+1]=top;
    }
}

}
i=len-1;
cnt=0;
while(prev[i]!=-2)
{
i=prev[i];
cnt++;
}
for(i=0;i<10;i++)
free(v[i]);
free(v);
cout<<cnt;
return 0;
}