题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=316#problem/I

code:

#include <stdio.h>
#include <stdlib.h>
int count=0;

struct SqStack
{
    int *base;
    int *top;
    int stacksize;
};

struct SqStack *init(int m)
{
    struct SqStack *p;
    p=(struct SqStack *)malloc(sizeof(struct SqStack));
    if(p!=NULL)
    {
            p->base=(int *)malloc(sizeof(int)*m);
            if(p->base!=NULL)
            {
                p->top=p->base;
                p->stacksize=m;
                return p;
            }
            else
                free(p);
    }
    printf("Out of space!\n");
    return NULL;
}//栈的初始化

int empty(struct SqStack *p)
{
    return p->base==p->top;
}//判断空栈

int full(struct SqStack *p)
{
    return p->top-p->base==p->stacksize;
}//判断满栈

int push(struct SqStack *p,int x)
{
    if(p->top-p->base<p->stacksize)
    {
        *(p->top)=x;
        p->top++;
        return 1;
    }
    printf("overflow!\n");
    return 0;
}//入栈

int pop(struct SqStack *p)
{
    return *(--p->top);
}//出栈

int top(struct SqStack *p)
{
    return *(p->top-1);
}//取栈顶元素

void dfs(struct SqStack *getin,struct SqStack *nth,struct SqStack *getout)
{
    if(empty(getin)&&empty(nth))//没有车在站内,也没有车等候
        count++;
    else
    {
        if(!empty(nth))//有车等候
        {
            push(getin,pop(nth));//让等候的车进栈
            dfs(getin,nth,getout);
            push(nth,pop(getin));
        }
        if(!empty(getin))//栈里有车
        {
            push(getout,pop(getin));//让车出栈
            dfs(getin,nth,getout);
            push(getin,pop(getout));
        }
    }
}
int main()
{
    struct SqStack *getin,*nth,*getout;//进栈,没事做等着,出栈
    int n,i;
    getin=init(100);
    nth=init(100);
    getout=init(100);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        push(nth,i);//所有车都等着
    dfs(getin,nth,getout);
    printf("%d",count);
    return 0;
}
菜鸟之作,仅供参考,如有错误,请您指出——Tamara

发表评论

电子邮件地址不会被公开。

Post Navigation