Untitled
unknown
abap
a year ago
6.7 kB
4
Indexable
Never
#include <stdio.h> #include <stdlib.h> #define tank_x 5 #define tank_y 6 #define tank_z 10 #define maxlength 100 #define goal 8 #define empty 0 typedef struct { int x; int y; int z; }State; void makenullState (State *state){ state->x = 0; state->y = 0; state->z = 0; } void printState (State state){ printf("X:%d \t Y:%d \t Z: %d", state.x, state.y, state.z); } const char* action[] = {"1st state", "pour water X to Y", "pour water X to Z", "pour water Y to X","pour water Y to Z", "pour water Z to X","pour water Z to Y"}; int goalcheck (State state){ return (state.x == goal || state.y == goal || state.z == goal); } int min (int a, int b){ return a < b ? a:b; } int max (int a, int b){ return a > b ? a:b; } int pourWaterX_Z (State cur_state, State *result){ if(cur_state.x > 0 && cur_state.z != tank_z){ result->z = min((cur_state.x + cur_state.z),tank_z); result->x = max((cur_state.x - (tank_z - cur_state.z)),0); result->y = cur_state.y; return 1; } return 0; } int pourWaterX_Y (State cur_state, State *result){ if(cur_state.x > 0 && cur_state.y != tank_y){ result->y = min((cur_state.y + cur_state.x),tank_y); result->x = max((cur_state.x - (tank_y - cur_state.y)),0); result->z = cur_state.z; return 1; } return 0; } int pourWaterY_Z (State cur_state, State *result){ if(cur_state.y > 0 && cur_state.z != tank_z){ result->z = min ((cur_state.y + cur_state.z),tank_z); result->y = max((cur_state.y - (tank_z - cur_state.z)),0); result->x = cur_state.x; return 1; } return 0; } int pourWaterY_X (State cur_state, State *result){ if(cur_state.y > 0 && cur_state.x != tank_x){ result->x = min((cur_state.x + cur_state.y),tank_x); result->y = max ((cur_state.y - (tank_x - cur_state.x)),0); result->z = cur_state.z; return 1; } return 0; } int pourWaterZ_X (State cur_state, State *result){ if(cur_state.z > 0 && cur_state.x != tank_x){ result->x = min ((cur_state.x + cur_state.z), tank_x); result->z = max((cur_state.z - (tank_x - cur_state.x)),0); result->y = cur_state.y; return 1; } return 0; } int pourWaterZ_Y (State cur_state, State *result){ if(cur_state.z > 0 && cur_state.y != tank_y){ result->y = min ((cur_state.z + cur_state.y),tank_y); result->z = max((cur_state.z - (tank_y - cur_state.y)),0); result->x = cur_state.x; return 1; } return 0; } int call_op (State cur_state, State *result, int opt){ switch(opt){ case 1: return pourWaterX_Y(cur_state, result); case 2: return pourWaterX_Z(cur_state, result); case 3: return pourWaterY_X (cur_state, result); case 4: return pourWaterY_Z (cur_state, result); case 5: return pourWaterZ_X (cur_state, result); case 6: return pourWaterZ_Y (cur_state, result); default: printf("Error"); } } typedef struct Node { State state; struct Node* Parent; int no_function; }Node; typedef struct { Node* Elements [maxlength]; int top_idx; }Stack; void makenullStack (Stack *stack){ stack->top_idx = maxlength; } int empty_stack (Stack stack){ return stack.top_idx == maxlength; } int full_stack (Stack s){ return s.top_idx == 0; } Node* top (Stack stack){ if(!empty_stack(stack)) return stack.Elements[stack.top_idx]; return NULL; } void push (Node* x, Stack *stack){ if(full_stack(*stack)) printf("Error! Stack full"); else{ stack->top_idx -= 1; stack->Elements[stack->top_idx] = x; } } void pop (Stack *stack){ if(!empty_stack(*stack)) stack->top_idx += 1; else printf("Error! Stack rong"); } int compareState (State s1, State s2){ return (s1.x == s2.x && s1.y == s2.y); } int find_state (State s, Stack openStack){ while (!empty_stack(openStack)){ if(compareState(top(openStack)->state,s)) return 1; pop(&openStack); } return 0; } //Node* DFS (State state){ // Stack open ; // Stack close; // makenullStack(&open); // makenullStack(&close); // // Node* root = (Node*) malloc (sizeof(Node)); // root->state = state; // root->Parent = NULL; // root->no_function = 0; // push(root, &open); // // while(!empty_stack(open)){ // Node* node = top (open); // pop(&open); // push(node, &close); // // if(goalcheck(node->state)) // return node; // int opt; // for(opt = 1; opt <= 6; opt++){ // State newstate; // makenullState(&newstate); // if(call_op(node->state, &newstate, opt)){ // if(find_state(newstate, close) || find_state(newstate, open)) // continue; // // Node* newNode = (Node*) malloc (sizeof(Node)); // newNode->state = newstate; // newNode->Parent = node; // newNode->no_function = opt; // push(newNode, &open); // } // } // } // return NULL; //} Node* DFS (State s){ Stack open; Stack close; makenullStack(&open); makenullStack(&close); Node* root = (Node*) malloc (sizeof(Node)); root->state = s; root->Parent = NULL; root->no_function = 0; push(root, &open); while(!empty_stack(open)){ Node* node = top(open); pop(&open); push(node, &close); if(goalcheck(node->state)) return node; int opt; for(opt = 1; opt <= 6; opt++){ State newState; makenullState(&newState); if(call_op(node->state,&newState,opt)){ printf("c"); if(find_state(newState, open) || find_state(newState, close)); continue; Node* newNode = (Node*) malloc (sizeof(Node)); newNode->state = newState; newNode->Parent = node; newNode->no_function = opt; push(newNode, &open); } } } return NULL; } //void print_Ways (Node* node){ // Stack stackPrint; // makenullStack(&stackPrint); // // while(node->Parent != NULL){ // push(node, &stackPrint); // node = node->Parent; // } // push(node , &stackPrint); // int no_action = 0; // while (!empty_stack(stackPrint)){ // printf("\nAction %d: %s \n", no_action, action[top(stackPrint)->no_function]); // printState(top(stackPrint)->state); // pop(&stackPrint); // no_action++; // } //} void print_Ways (Node* node){ Stack stackPrint; makenullStack(&stackPrint); while(node->Parent != NULL){ push(node, &stackPrint); node = node->Parent; } push(node , &stackPrint); int no_action = 0; while (!empty_stack(stackPrint)){ printf("\nAction %d: %s \n", no_action, action[top(stackPrint)->no_function]); printState(top(stackPrint)->state); pop(&stackPrint); no_action++; } } int main (){ State cur_state = {0,0,10}; Node* p = DFS(cur_state); printState(p->state); //print_Ways(p); return 0; }