101 - The Blocks Problem

문제원문 : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37

이 문제는 다음과 같은 특성을 예외 처리를 잘 하면 구현 할 수 있는 문제이다.

move a onto b - a와 b블럭위에 다른 블럭들을 원래 위치로 돌려 보내고 a를 b 위로 옮긴다

move a over b - a블럭 위에 다른 블럭을 원래 위치로 돌려보내고 a를 b 위로 옮긴다.

pile a onto b - b블럭 위에 다른 블럭을 원래 위치로 보내고 a를 b위로 옮긴다.

pile a over b - a를 b블럭으로 옮긴다.

quit - 최종 상태를 출력한다.

같은 블럭의 명령, 같은 블럭이 있는 경우, 그외 무시한다.

리스트를 이용하여 각 노드를 연결하고 만약 블록이 가장 아래에 있다면 즉 lLink가 존재 하지 않는 값만 출력하도록 하면 되는 문제이다.

#include<stdio.h> #include<stdlib.h> #include<string.h> #define null 0 typedef struct _node{ int data; struct _node* llink, *rlink; } Node; Node* createNode(int data){ Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->llink = 0; newNode->rlink = 0; return newNode; } void insertNode(Node* N, Node* next){ N->rlink = next; next->llink = N; } int searchNode(Node* N, Node* Target){ if (N->data == Target->data){ return 1; } else{ if (N->rlink != null){ return searchNode(N->rlink, Target); } else{ return 0; } } } void recallBlock(Node* N){ if (N->rlink != null){ recallBlock(N->rlink); } if (N->llink != null){ N->llink->rlink = null; N->llink = null; } } Node* endNode(Node* N){ if (N->rlink != null){ return endNode(N->rlink); } else { return N; } } void move_onto(Node* a, Node* b){ recallBlock(a); recallBlock(b); b->rlink = a; if (a->llink != null){ a->llink->rlink = null; } a->llink = b; } void move_over(Node* a, Node* b){ Node* end = endNode(b); recallBlock(a); end->rlink = a; if (a->llink != null){ a->llink->rlink = null; } a->llink = end; } void pile_onto(Node* a, Node* b){ recallBlock(b); b->rlink = a; if (a->llink != null){ a->llink->rlink = null; } a->llink = b; } void pile_over(Node* a, Node* b){ Node* end = endNode(b); end->rlink = a; if (a->llink != null){ a->llink->rlink = null; } a->llink = end; } void printBlock(Node* N){ printf(" %d", N->data); if (N->rlink != null){ printBlock(N->rlink); } } int main(void){ int count, inst, block[2], i; char str[2][5]; Node* B[25]; scanf("%d", &count); for (i = 0; i < count; i++){ B[i] = createNode(i); } while (1){ scanf("%s", str[0]); if (strcmp(str[0], "quit") == 0){ for (i = 0; i < count; i++){ printf("%d:", i); if (B[i]->llink == null){ printBlock(B[i]); } printf("\n"); } for (i = 0; i < count; i++){ free(B[i]); } return 0; } scanf("%d %s %d", &block[0], str[1], &block[1]); if (strcmp(str[0], "move") == 0){ if (strcmp(str[1], "onto") == 0){ inst = 1; } else if (strcmp(str[1], "over") == 0){ inst = 2; } else{ continue; } } else if (strcmp(str[0], "pile") == 0){ if (strcmp(str[1], "onto") == 0){ inst = 3; } else if (strcmp(str[1], "over") == 0){ inst = 4; } else{ continue; } } if (searchNode(B[block[0]], B[block[1]])){ continue; } else if (searchNode(B[block[1]], B[block[0]])){ continue; } switch (inst){ case 1: move_onto(B[block[0]], B[block[1]]); break; case 2: move_over(B[block[0]], B[block[1]]); break; case 3: pile_onto(B[block[0]], B[block[1]]); break; case 4: pile_over(B[block[0]], B[block[1]]); break; } } }