`
dnstfengtao
  • 浏览: 19065 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

HDU1022(Train Problem I)

 
阅读更多
Problem Description
As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.



Input
The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.


Output
The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.


Sample Input

3 123 321
3 123 312

Sample Output

Yes.
in
in
in
out
out
out
FINISH
No.
FINISH

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define STACK_INTI_SIZE 100
#define STACK_INCREMENT 10

typedef int Status;
typedef char SElemType;
typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

Status initStack(SqStack *s)
{
	s->base = (SElemType *)malloc(STACK_INTI_SIZE * sizeof(SElemType));	
	
	if(!s->base)
	{
		exit(OVERFLOW);
	}
	
	s->top = s->base;

	s->stacksize = STACK_INTI_SIZE;
	
	return OK;
}

Status destoryStack(SqStack *s)
{
	free(s->base);
	s->base = NULL;
	s->top = NULL;
	s->stacksize = 0;
	return OK;
}

Status clearStack(SqStack *s)
{
	s->top = s->base;
	s->stacksize = STACK_INTI_SIZE;
	return OK;
} 

Status getTop(SqStack *s,SElemType *e)
{
	if(s->top == s->base)
	{
		return ERROR;
	}

	*e = *(s->top - 1);

	return OK;
}

Status push(SqStack *s,SElemType e)
{
	if(s->top - s->base >= s->stacksize)
	{
		s->base = (SElemType *)realloc(s->base,(s->stacksize + STACK_INCREMENT) * sizeof(SElemType));
		
		if(!s->base)
		{
			exit(OVERFLOW);
		}

		s->top = s->base + s->stacksize;

		s->stacksize += STACK_INCREMENT;
	}

	*s->top = e;

	s->top ++;

	return OK;
}

Status pop(SqStack *s,SElemType *e)
{
	if(s->top == s->base)
	{
		return ERROR;
	}
	
	s->top --;

	*e = *s->top;

	return OK;
}

int isEmpty(SqStack s)
{
	if(s.top == s.base)
	{
		return 1;
	}else
	{
		return 0;
	}
}

int main()
{
	SqStack s;
	int n;
	initStack(&s);
	while(scanf("%d",&n) != EOF)
	{
		char begin[9];
		char end[9];
		int inout[18];
		int len,i,j;

		scanf("%s",begin);
		scanf("%s",end);
		len = strlen(begin);

		//声明一个j来单独记录火车出站下标
		for(i = 0,j = 0; i < len; i++)
		{
			char e;

			push(&s,begin[i]);
			inout[i+j] = 1;

			while(!isEmpty(s))
			{
				getTop(&s,&e);

				if(e == end[j])
				{
					pop(&s,&e);
					inout[i + j + 1] = 0;
					j++;
				}else
				{
					break;
				}
			}
		}

		if(j == len)
		{
			printf("Yes.\n");
			for(i = 0; i < (len*2); i++)
			{
				if(inout[i] == 1)
				{
					printf("in\n");
				}else
				{
					printf("out\n");
				}
			}
			printf("FINISH\n");
		}else
		{
			printf("No.\n");
			printf("FINISH\n");
		}
		clearStack(&s);
	}
	destoryStack(&s);
	return 0;
}


基本思路:自己构造了一个栈,用来模仿火车进出站点操作。
由于要匹配输出序列,基本思路先将输入的第一个值入栈,
然后取栈头和输出序列比较,相同则出栈,否则继续将输入
序列中的值入栈,再次比较,和上面思路基本相同。比较完
如果比较到输出序列的末尾则该序列可由输入序列经过栈操
表示同时记录出入操作,否则失败,算法完毕。
  • 大小: 23 KB
分享到:
评论

相关推荐

    HDU 1022 Train Problem I 附详细思路

    HDU 1022 Train Problem I 附详细思路

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    14. **IO与NIO**:Java的I/O流系统以及新推出的非阻塞I/O(New IO,即NIO)。 15. **设计模式**:面向对象编程中的常见设计模式,如单例、工厂、观察者、装饰器等,可以提高代码的可读性和可维护性。 以上就是根据...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    ACM HDU题目分类

    ACM HDU 题目分类 ...1022 数据结构的题(栈的应用);1030 简单题,可用模拟过 等等。 ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu2101解决方案

    hdu2101AC代码

    hdu动态规划算法集锦

    - 状态转移方程:$f[j] = \max\{f[j], f[j - q[i].money] + q[i].v\}$,其中$q[i].money$是第$i$个地点的价值,$q[i].v$是第$i$个地点的花费。 - 初始条件:$f[0] = 1$(不抢劫任何地方的情况)。 #### 3A:100A:...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    HDU图论题目分类

    * 题目1026:Ignatius and the Princess I,涉及到完全搜索的概念。 2. 图的遍历:深度优先搜索(DFS)、广度优先搜索(BFS)等。 * 题目1043:Eight,涉及到多种解决方法。 * 题目1044:Collect More Jewels,涉及...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    解题代码 hdu1241

    根据给定的文件信息,我们可以得知这是一段用于解决HDU(Hdu Online Judge)编号为1241的问题的代码。该代码主要采用了深度优先搜索(DFS)算法来解决问题。 #### 二、DFS(Depth First Search)算法原理 **定义:...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

Global site tag (gtag.js) - Google Analytics