SHARE
TWEET

Untitled

a guest Jan 11th, 2017 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  
  5. #define HEIGHT 10
  6. #define WIDTH 10
  7.  
  8. struct node {
  9.     int mode;
  10.     struct node *up;
  11.     struct node *left;
  12.     struct node *down;
  13.     struct node *right;
  14.     struct node *next;
  15. };
  16.  
  17. //Handles the queue
  18. struct node *ptrCurrent = NULL; //First in que
  19. struct node *ptrLast = NULL; //Last added in que
  20. //-----------------------------
  21.    
  22. int bfs(void);
  23. void setupMatrix(struct node matrix[HEIGHT][WIDTH]);
  24. void printMatrix(struct node matrix[HEIGHT][WIDTH]);
  25.  
  26. int main()
  27. {
  28.     struct node matrix[HEIGHT][WIDTH];
  29.    
  30. setupMatrix(matrix);
  31.     //Tweak it to setup the puzzle
  32.     //Search from point:
  33.     int beginY = 0;
  34.     int beginX = 0;
  35.     //Destination point:
  36.     int desinY = 2;
  37.     int destinX = 2;
  38.     //----------------------------
  39.     matrix[desinY][destinX].mode = 1; //Destination: mode1
  40.     matrix[beginY][beginX].mode = 3; //Begining: mode3
  41.  
  42.     //WALL: (make a function that draws a wall from two points)
  43.     //matrix[0][1].mode = 3;
  44.     //matrix[1][1].mode = 3;
  45.     //matrix[1][0].mode = 3;
  46.     //---------------------------------------------------------
  47.  
  48.  
  49.     //Inicialise the queue from the begining node
  50.     ptrCurrent = &matrix[beginY][beginX];
  51.     ptrLast = &matrix[beginY][beginX];
  52.     //--------------------
  53.  
  54.     //START:
  55.     int tries = bfs();
  56.  
  57.     //Check
  58.     printf("Tries = %dn", tries);
  59.  
  60.     //When something unexpected happends
  61.     if(tries == 0) {
  62.         printf("ERROR BFSn");
  63.         return -1;
  64.     }
  65.     //----------------------------------
  66.  
  67.     //When finished:
  68.     printMatrix(matrix); //Mode5 represents the found solution
  69.     system("PAUSE");
  70.     return 0;
  71. }
  72.  
  73. int bfs(void)
  74. {
  75.     //Use to test
  76.     int tries = 0;
  77.  
  78.     while(1)
  79.     {
  80.         ptrCurrent->mode = 3;
  81.         if(ptrCurrent->up != NULL)
  82.         {
  83.             if(ptrCurrent->up->mode == 1)
  84.             {
  85.                 printf("Found the solutionn");
  86.                 ptrCurrent->up->mode = 5;
  87.                 return tries;//break;
  88.             }
  89.             else if(ptrCurrent->up->mode == 0)
  90.             {
  91.                 ptrCurrent->next = ptrCurrent->up;
  92.                 ptrLast = ptrCurrent->up;
  93.             }
  94.         }
  95.  
  96.         if(ptrCurrent->left != NULL)
  97.         {
  98.             if(ptrCurrent->left->mode == 1)
  99.             {
  100.                 printf("Found the solutionn");
  101.                 ptrCurrent->left->mode = 5;
  102.                 return tries;//break;
  103.             }
  104.             else if(ptrCurrent->left->mode == 0)
  105.             {
  106.                 ptrCurrent->next = ptrCurrent->left;
  107.                 ptrLast = ptrCurrent->left;
  108.             }
  109.         }
  110.  
  111.         if(ptrCurrent->down != NULL)
  112.         {
  113.             if(ptrCurrent->down->mode == 1)
  114.             {
  115.                 printf("Found the solutionn");
  116.                 ptrCurrent->down->mode = 5;
  117.                 return tries;//break;
  118.             } else if(ptrCurrent->down->mode == 0)
  119.             {
  120.                 ptrCurrent->next = ptrCurrent->down;
  121.                 ptrLast = ptrCurrent->down;
  122.             }
  123.         }
  124.  
  125.         if(ptrCurrent->right != NULL) {
  126.             if(ptrCurrent->right->mode == 1)
  127.             {
  128.                 printf("Found the solutionn");
  129.                 ptrCurrent->right->mode = 5;
  130.                 return tries;//break;
  131.             }
  132.             else if(ptrCurrent->right->mode == 0)
  133.             {
  134.                 ptrCurrent->next = ptrCurrent->right;
  135.                 ptrLast = ptrCurrent->right;
  136.             }
  137.         }
  138.         if(tries > (HEIGHT * WIDTH)) {
  139.             system("ERROR");
  140.             return 0;
  141.         }
  142.         ptrCurrent = ptrCurrent->next;
  143.         tries++;
  144.  
  145.     }
  146.     return 0;
  147. }
  148.  
  149. void setupMatrix(struct node matrix[HEIGHT][WIDTH])
  150. {
  151.     int i,j;
  152.  
  153.     for(j = 0; j < HEIGHT; j++)
  154.     {
  155.         for(i = 0; i < WIDTH; i++)
  156.         {
  157.             //All nodes.mode is set to 0, this can be changed later
  158.             matrix[j][i].mode = 0;
  159.             //All nodes.next is set to NULL, this pointer is only for linked list purposes
  160.             matrix[j][i].next = NULL;
  161.  
  162.             //Connect UP
  163.             if(j == 0)
  164.                 matrix[j][i].up = NULL;
  165.             else
  166.                 matrix[j][i].up = &matrix[j-1][i];
  167.  
  168.             //Connect LEFT
  169.             if(i == 0)
  170.                 matrix[j][i].left = NULL;
  171.             else
  172.                 matrix[j][i].left = &matrix[j][i-1];
  173.  
  174.             //Connect DOWN
  175.             if(j == HEIGHT-1)
  176.                 matrix[j][i].down = NULL;
  177.             else
  178.                 matrix[j][i].down = &matrix[j+1][i];
  179.  
  180.             //Connect RIGHT
  181.             if(i == WIDTH-1)
  182.                 matrix[j][i].right = NULL;
  183.             else
  184.                 matrix[j][i].right = &matrix[j][i+1];
  185.  
  186.         }
  187.     }
  188. }
  189.    
  190. ptrCurrent->next = ptrCurrent->up;
  191.    
  192. ptrLast->next = ptrCurrent->up;
RAW Paste Data
Top