題目描述見：uva 101 or poj 1208

關(guān)鍵在于徹底理解題目中搬積木的幾個(gè)命令的含義，見具體分析

如果還不能理解題意，那么找一個(gè)正確通過的代碼，編譯并輸入測(cè)試數(shù)據(jù)，查看其每一個(gè)命令的執(zhí)行情況。如我的代碼中162行注釋內(nèi)容取消后即可顯示每一步執(zhí)行后當(dāng)前積木的情況）

這個(gè)題目似乎沒有合適的數(shù)據(jù)結(jié)構(gòu)，由于插入刪除操作較多，所以直接用了鏈表，并且使用雙重指針，差點(diǎn)把自己搞暈。（另外，剛開始寫的代碼能在poj1208上通過，但不能在uva 101上通過，后來發(fā)現(xiàn)是141行中的continue誤寫成了break。網(wǎng)上也有類似的情況，似乎是因?yàn)闆]有考慮到特殊情況的處理（即兩個(gè)積木塊號(hào)相同或者處于同一列時(shí)需要忽略該命令））

相關(guān)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;}elsetmpBlk = 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; } ?

?另外一種方案（使用棧進(jìn)行操作）：

#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);}elsereturn 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);}elsereturn 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;elsereturn 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; }

總結(jié)

以上是生活随笔為你收集整理的the blocks problem(uva 101 or poj 1208)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。