- 浏览: 70388 次
- 性别:
- 来自: 杭州
最新评论
关键在于彻底理解题目中搬积木的几个命令的含义,见具体分析
如果还不能理解题意,那么找一个正确通过的代码,编译并输入测试数据,查看其每一个命令的执行情况。如我的代码中162行注释内容取消后即可显示每一步执行后当前积木的情况)
这个题目似乎没有合适的数据结构,由于插入删除操作较多,所以直接用了链表,并且使用双重指针,差点把自己搞晕。(另外,刚开始写的代码能在poj1208上通过,但不能在uva 101上通过,后来发现是141行中的continue误写成了break。网上也有类似的情况,似乎是因为没有考虑到特殊情况的处理(即两个积木块号相同或者处于同一列时需要忽略该命令))
相关C语言代码:
/* uva 101 or poj 1208 */ /*the Blocks problem */ #include <stdio.h> #include <stdlib.h> #include <string.h> struct node { int data; struct node *prev; struct node *next; }; typedef struct node *pBlock; static void CreateHeader(pBlock *ppBlk) { pBlock newBlk = malloc(sizeof(*newBlk)); newBlk -> next = newBlk->prev = NULL; (*ppBlk) = newBlk; } static void InsertOnFirst(pBlock *ppBlk, int data) { pBlock newBlk = malloc(sizeof(*newBlk)); newBlk -> data = data; newBlk -> next = NULL; newBlk -> prev = *ppBlk; (*ppBlk)->next = newBlk; } static int FindBlock(pBlock *ppBlk, int blockNumber, pBlock *ppretBlock) { pBlock tmpBlk = (*ppBlk)->next; while(tmpBlk != NULL) if(tmpBlk->data == blockNumber) { *ppretBlock = tmpBlk; return 1; } else tmpBlk = tmpBlk->next; return 0; } static void PopAllFollowBlks(pBlock *ppBTab,pBlock *ppBlk) { pBlock tmpBlk,curBlk = (*ppBlk)->next; (*ppBlk)->next = NULL; while(curBlk != NULL) { tmpBlk = curBlk; curBlk = curBlk->next; ppBTab[tmpBlk->data] ->next = tmpBlk; tmpBlk->next = NULL; tmpBlk->prev = ppBTab[tmpBlk->data]; } } static void MoveOnto(pBlock *ppBTab,pBlock *ppSrcBlk, pBlock *ppDstBlk) { PopAllFollowBlks(ppBTab,ppSrcBlk); PopAllFollowBlks(ppBTab,ppDstBlk); /*pBlock pSrcTmpBlk = pSrcBlk->next,pDstTmpBlk=pDstBlk->next;*/ (*ppSrcBlk)->prev->next = NULL; (*ppSrcBlk) ->next = (*ppDstBlk)->next; (*ppSrcBlk)->prev = (*ppDstBlk); (*ppDstBlk)->next = (*ppSrcBlk); } static void MoveOver(pBlock *ppBTab,pBlock *ppSrcBlk, pBlock *ppDstBlk) { pBlock lastDstBlk = (*ppDstBlk); PopAllFollowBlks(ppBTab,ppSrcBlk); (*ppSrcBlk)->prev->next = NULL; while(lastDstBlk->next != NULL) lastDstBlk = lastDstBlk->next; (*ppSrcBlk)->next = lastDstBlk->next; (*ppSrcBlk)->prev = lastDstBlk; lastDstBlk->next = (*ppSrcBlk); } static void PileOnto(pBlock *ppBTab,pBlock *ppSrcBlk, pBlock *ppDstBlk) { PopAllFollowBlks(ppBTab,ppDstBlk); (*ppSrcBlk)->prev->next = NULL; (*ppDstBlk)->next = *ppSrcBlk; (*ppSrcBlk)->prev = *ppDstBlk; } static void PileOver(pBlock *ppBTab,pBlock *ppSrcBlk, pBlock *ppDstBlk) { pBlock lastDstBlk = (*ppDstBlk); (*ppSrcBlk)->prev->next = NULL; while(lastDstBlk->next != NULL) lastDstBlk = lastDstBlk->next; (*ppSrcBlk)->prev = lastDstBlk; lastDstBlk->next = (*ppSrcBlk); } static void PrintBlock(pBlock pBlk) { pBlock tmpBlk = (pBlk) -> next; while(tmpBlk != NULL) { printf(" %d",tmpBlk->data); tmpBlk = tmpBlk -> next; } printf("\n"); } static void PrintBlks(pBlock *ppBlk, int arraysize) { int i; for(i = 0; i < arraysize; i++) { printf("%d:",i); PrintBlock(ppBlk[i]); } } int main(void) { int n; pBlock *ppBlks,pSrcBlk,pDstBlk; char str1[10],str2[10]; int fstBlkNum,scdBlkNum,i,j; int isFound1, isFound2; scanf("%d",&n); getchar(); ppBlks = malloc(n * sizeof(*ppBlks)); for(i = 0; i < n; i++) { CreateHeader(&ppBlks[i]); InsertOnFirst(&ppBlks[i],i); } /* PrintBlks(ppBlks,n);*/ while(1) { scanf("%s",str1); if(strcmp(str1,"quit") == 0) break; scanf("%d %s %d",&fstBlkNum,str2,&scdBlkNum); if(fstBlkNum == scdBlkNum) continue; for(i = 0; i < n; i++) { isFound1 = FindBlock(&ppBlks[i],fstBlkNum,&pSrcBlk); if(isFound1) break; } for(j = 0; j < n; j++) { isFound2 = FindBlock(&ppBlks[j],scdBlkNum,&pDstBlk); if(isFound2) break; } if(i != j && strcmp(str1,"move") == 0 && strcmp(str2,"onto") == 0) MoveOnto(ppBlks,&pSrcBlk,&pDstBlk); else if(i != j && strcmp(str1,"move") == 0 && strcmp(str2,"over") == 0) MoveOver(ppBlks,&pSrcBlk,&pDstBlk); else if(i != j && strcmp(str1,"pile") == 0 && strcmp(str2,"onto") == 0) PileOnto(ppBlks,&pSrcBlk,&pDstBlk); else if(i != j && strcmp(str1,"pile") == 0 && strcmp(str2,"over") == 0) PileOver(ppBlks,&pSrcBlk,&pDstBlk); /* PrintBlks(ppBlks,n);*/ } PrintBlks(ppBlks,n); return 0; }
另外一种方案(使用栈进行操作):
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MINSTACKSIZE 30 #define STACKINCREMENT 30 struct stack{ int capacity; int top; int *array; }; typedef struct stack Stack; Stack *CreateStack() { Stack *pStk = malloc(sizeof(*pStk)); pStk->array = malloc(MINSTACKSIZE*sizeof(*(pStk->array))); if(pStk->array == NULL) { fprintf(stderr,"error:no space to allocate.\n"); exit(EXIT_FAILURE); } else { pStk->capacity = MINSTACKSIZE; pStk->top = 0; } return pStk; } int IsStackEmpty(Stack *pStk) { return pStk->top == 0; } int IsStackFull(Stack *pStk) { return pStk->capacity == pStk->top + 1; } int Push(Stack *pStk, int data) { if(IsStackFull(pStk)) { pStk->array = realloc(pStk, (pStk->capacity+STACKINCREMENT)* sizeof(*(pStk->array))); if(pStk->array == NULL) { fprintf(stderr, "error: no space to allocate\n"); exit(EXIT_FAILURE); } else { pStk -> capacity += STACKINCREMENT; } } pStk -> array[++(pStk -> top)] = data; return 0; } int Pop(Stack *pStk) { if(IsStackEmpty(pStk)) { fprintf(stderr,"error: empty stack can pop nothing\n"); exit(EXIT_FAILURE); } else return pStk->array[(pStk -> top) --] ; } int Top(Stack *pStk) { if(IsStackEmpty(pStk)) { fprintf(stderr,"error: empty stack don't have top element\n"); exit(EXIT_FAILURE); } else return pStk->array[pStk -> top] ; } int Find(Stack *pStk, int data) { int i; for(i = 1; i <= pStk->top; i++) if(pStk -> array[i] == data) break; if(i > pStk->top) return 0; else return i; } int PopFollowingBack(Stack **ppStkArray, int index, int pos) { Stack *pCurStk = ppStkArray[index]; int curData; while(pCurStk -> top > pos) { curData = Pop(pCurStk); /* pTmpStk = ppStkArray[curData];*/ Push(ppStkArray[curData],curData); } return 0; } int PushCurAndFollowing(Stack **ppStkArray, int srcIndex, int srcPos, int dstIndex, int dstPos) { int i,srcTop = ppStkArray[srcIndex] -> top; for(i = srcPos; i <= srcTop; i++) { Push(ppStkArray[dstIndex],ppStkArray[srcIndex]->array[i]); } ppStkArray[srcIndex] -> top -= srcTop - srcPos + 1; return 0; } int MoveOnto(Stack **ppStkArray,int srcIndex,int srcPos, int dstIndex,int dstPos) { PopFollowingBack(ppStkArray,srcIndex,srcPos); PopFollowingBack(ppStkArray,dstIndex,dstPos); PushCurAndFollowing(ppStkArray,srcIndex,srcPos,dstIndex,dstPos); return 0; } int MoveOver(Stack **ppStkArray,int srcIndex,int srcPos, int dstIndex,int dstPos) { PopFollowingBack(ppStkArray,srcIndex,srcPos); PushCurAndFollowing(ppStkArray,srcIndex,srcPos,dstIndex,dstPos); return 0; } int PileOnto(Stack **ppStkArray,int srcIndex,int srcPos, int dstIndex, int dstPos) { PopFollowingBack(ppStkArray,dstIndex,dstPos); PushCurAndFollowing(ppStkArray,srcIndex,srcPos,dstIndex,dstPos); return 0; } int PileOver(Stack **ppStkArray,int srcIndex,int srcPos, int dstIndex,int dstPos) { PushCurAndFollowing(ppStkArray,srcIndex,srcPos,dstIndex,dstPos); return 0; } void PrintStack(Stack *pStk) { int i; for(i = 1; i <= pStk->top; i++) printf(" %d",pStk->array[i]); printf("\n"); } void PrintAllBlocks(Stack **ppStk, int blockNum) { int i; for(i = 0; i < blockNum; i++) { printf("%d:",i); PrintStack(ppStk[i]); } } int main(void) { Stack **ppStkArray; int n; int i,j; char str1[10],str2[10]; int srcData,dstData; int srcPos,dstPos; scanf("%d",&n); ppStkArray = malloc(n*sizeof(*ppStkArray)); for(i = 0; i < n; i++) { ppStkArray[i] = CreateStack(); Push(ppStkArray[i],i); } /* PrintAllBlocks(ppStkArray,n); printf("after popping %d\n",Pop(ppStkArray[2])); PrintAllBlocks(ppStkArray,n);*/ while(1) { scanf("%s",str1); if(strcmp(str1,"quit")==0) break; scanf("%d %s %d",&srcData,str2,&dstData); if(srcData == dstData) continue; for(i = 0; i < n; i++) { srcPos = Find(ppStkArray[i],srcData); if(srcPos) break; } for(j = 0; j < n; j++) { dstPos = Find(ppStkArray[j],dstData); if(dstPos) break; } if(i == j) continue; else { if(strcmp(str1,"move") == 0 && strcmp(str2, "onto") == 0) MoveOnto(ppStkArray,i,srcPos,j,dstPos); else if(strcmp(str1,"move") == 0 && strcmp(str2, "over") == 0) MoveOver(ppStkArray,i,srcPos,j,dstPos); else if(strcmp(str1,"pile") == 0 && strcmp(str2, "onto") == 0) PileOnto(ppStkArray,i,srcPos,j,dstPos); else if(strcmp(str1,"pile") == 0 && strcmp(str2, "over") == 0) PileOver(ppStkArray,i,srcPos,j,dstPos); /*PrintAllBlocks(ppStkArray,n);*/ } } PrintAllBlocks(ppStkArray,n); return 0; }
发表评论
-
最小c编译器
2011-11-08 14:09 1420最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1094c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1722程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1320参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6277试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1090现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1770fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2115很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4543csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:56 0题目描述见:uva 101 or poj 1208 ... -
部分排序算法c语言实现
2011-09-02 14:51 988代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错 ... -
编译器开发相关资源
2011-08-31 08:40 1167开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 940题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1088 System Overload
2011-07-23 17:30 1137约瑟夫环 (josephus problem )问题, ... -
zoj 1091 Knight Moves
2011-07-23 09:05 814题目见zoj 1091 使用宽度搜索优先来求解, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1118题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 900题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 965题目见zoj 3488 很简单的题目,却没能一次搞定,因 ... -
zoj 1005 jugs
2011-07-22 11:43 806题目内容见zoj1005 由于A,B互素且A的容 ...
相关推荐
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
1390--blocks.rar
题面
the_building_blocks
The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.
The book is good as far as message it is conveying but the problem is that the layout tool has to be "very very" good in handling the layouts. At this point, there are no commercial tools for doing ...
new_blocks_for_the_kids
Frotran语言的编辑,修改,应用。C/C++, python, the open source
Templates for the Solution of Linear Systems - Building Blocks for Iterative Methods.ps
The Building Blocks of Experience An Early Framework for Interaction Designers
这是一个编译过后的scratch-blocks源码,可以直接使用 如果不能直接下载请私信我。
Stack Blocks - A Unity 3d Game The game is inspired from the game "Stack" . Screenshots
Built-In Building Blocks.dotx office2016 .
code blocks
intel thread building blocks
Embedded Systems Building Blocks
抽象精品ppt模板the_building_blocks062
ios Blocks 编程要点 深层 详细讲解
原来只有sqlserver的oracleMicrosoft.ApplicationBlocks.Data 现在oracle版的也有了