Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.4 kB
2
Indexable
Never
#include<stdio.h>
#include<stdlib.h>

typedef struct _Node {
    int left;
    int right;
    int up;
    int gone;
    struct _Node *left_link;
    struct _Node *right_link;
    struct _Node *up_link;
}Node;

Node *a[3005];
char output[30005];
int count;
int end;

void solve(int x,int y);

int main()
{
    int n,m;
    int x,y;
    int i,j;

    scanf("%d",&n);

    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[i]=(Node*)malloc(sizeof(Node)*1);
        a[i]->left=x;
        a[i]->right=y;
    }

    for(i=1;i<=n;i++)
    {
        if(a[i]->left !=0)
        {
            a[a[i]->left]->up_link=a[i];
            a[a[i]->left]->up=i;
            a[i]->left_link=a[a[i]->left];
        }
        if(a[i]->right !=0)
        {
            a[a[i]->right]->up_link=a[i];
            a[a[i]->right]->up=i;
            a[i]->right_link=a[a[i]->right];
        }
    }
    

    scanf("%d",&m);

    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            a[j]->gone=0;
        }
        end=0;
        for(j=0;j<count;j++)
        {
            output[j]=0;
        }
        count=0;
        scanf("%d%d",&x,&y);
        a[x]->gone=1;
        solve(x,y);
    }


}

void solve(int x,int y)
{
    int i;
    if(end) return;
    if(x==y)
    {
        
        for(i=0;i<count;i++)
        {
            printf("%c",output[i]);
        }
        printf("\n");
        end=1;
        return;
    }
    if(a[x]->left!=0)
    {
        if( a[x]->left_link->gone==0)
        {
            output[count]='L';
            count++;
            a[a[x]->left]->gone=1;
            solve(a[x]->left,y);
            a[a[x]->left]->gone=0;
            count--;
            output[count]=0;
        }
    }
    if(a[x]->right!=0)
    {
        if(a[x]->right_link->gone==0)
        {
            output[count]='R';
            count++;
            a[a[x]->right]->gone=1;
            solve(a[x]->right,y);
            a[a[x]->right]->gone=0;
            count--;
            output[count]=0;
        }
    }
    if(a[x]->up!=0)
    {
        if(a[x]->up_link->gone==0)
        {
            output[count]='P';
            count++;
            a[a[x]->up]->gone=1;
            solve(a[x]->up,y);
            a[a[x]->up]->gone=0;
            count--;
            output[count]=0;
        }
    }
}