SHARE
TWEET

Untitled

a guest Apr 18th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include < string.h >
  3. #define NMAX 100
  4. #define N 64
  5.  
  6. struct stack
  7. {
  8.     int elem[NMAX];
  9.     int top;
  10. };
  11.  
  12. void init(struct stack *stk) {
  13.     stk->top = 0;
  14. }
  15. void func(int num_start, int num_end, int minway, int a[N][N], int b[N], struct stack *stk)
  16. {
  17.     int i, j, way = 1, check = 0, del;
  18.     i = num_start;
  19.     while (i)
  20.     {
  21.         if (b[i] == way - 1)
  22.         {
  23.             check = 0;
  24.             way = way - 1;
  25.  
  26.         }
  27.         for (j = 0; j < 64; j++)
  28.         {
  29.             if (way != minway)
  30.             {
  31.                 if (a[i][j] == 1 && b[j] == 0)
  32.                 {
  33.                     push(stk, j);
  34.                     b[j] = way;
  35.                 }
  36.             }
  37.             else
  38.             {
  39.                 if (a[i][j] == 1 && j = num_end)
  40.                 {
  41.                     check = 1;
  42.                     func_print_way(b[64], stk, way);
  43.                     break;
  44.                 }
  45.                 else
  46.                     check = -1;
  47.             }
  48.         }
  49.         if (check == 1)
  50.             break;
  51.         if (check == -1)
  52.         {
  53.             del = pop(stk);
  54.             i = gettop(stk);
  55.         }
  56.         if (check == 0);
  57.         way++;
  58.         i = gettop(stk);
  59.     }
  60.     return;
  61. }
  62. void func_print_way(int b[64], struct stact *stk, int way)
  63. {
  64.     int i, k, x1, y1,del;
  65.     char word;
  66.     k = pop(stk);
  67.     y1 = (k % 8);
  68.     x1 =((int) k/8)+1;
  69.     word=reidentity(y1);
  70.     printf("%c %i", y1, x1);
  71.     while (i!=0)
  72.     {
  73.         k = gettop(stk);
  74.         if (b[k] == way - 1)
  75.             del = pop(stk);
  76.         else
  77.         {
  78.             way--;
  79.             y1 = (k % 8);
  80.             x1 = ((int)k / 8) + 1;
  81.             word = reidentity(y1);
  82.             printf("%c %i", y1, x1);
  83.             del=pop(stk);
  84.             i = way;
  85.  
  86.         }
  87.     }
  88.     return;
  89. }
  90. char reidentity(int y)
  91. {
  92.     char word;
  93. switch (y)
  94. {
  95.     case 1: word = 'A'; break;
  96.     case 2: word = 'B'; break;
  97.     case 3: word = 'C'; break;
  98.     case 4: word = 'D'; break;
  99.     case 5: word = 'E'; break;
  100.     case 6: word = 'F'; break;
  101.     case 7: word = 'G'; break;
  102.     case 8: word = 'H'; break;
  103. }
  104.     return word;
  105. }
  106. int identity(char word1)
  107. {
  108.     int x1;
  109.     switch (word1)
  110.     {
  111.     case 'A': x1 = 0; break;
  112.     case 'B': x1 = 1; break;
  113.     case 'C': x1 = 2; break;
  114.     case 'D': x1 = 3; break;
  115.     case 'E': x1 = 4; break;
  116.     case 'F': x1 = 5; break;
  117.     case 'G': x1 = 6; break;
  118.     case 'H': x1 = 7; break;
  119.     }
  120.         return x1;
  121. }
  122.  
  123. void push(struct stack *stk, int f) {
  124.     if (stk->top < NMAX) {
  125.         stk->elem[stk->top] = f;
  126.         stk->top++;
  127.     }
  128.     else
  129.         printf("Стек полон, количество элементов: %d !\n", stk->top);
  130. }
  131.  
  132. int pop(struct stack *stk)
  133. {
  134.     if ((stk->top) > 0)
  135.     {
  136.         return(stk->elem[stk->top - 1]);
  137.     }
  138. }
  139.  
  140. int gettop(struct stack *stk)
  141. {
  142.     return(stk->top);
  143. }
  144. int search_minway(int a[64][64], int number_start, int number_end) {
  145.  
  146.     int t, r, k, n, i, j, c[64][64];
  147.     n = 64; // Число Вершин
  148.  
  149.     for (i = 0; i < n; i++) {
  150.         for (j = 0; j < n; j++) {
  151.             if (a[i][j] == 0 && i != j) { // Если не диагональ
  152.                 a[i][j] = 16000; // Во Все не заполненные пихаем бескоечность
  153.             }
  154.         }
  155.     }
  156.  
  157.     for (i = 0; i < n; i++) {
  158.         for (j = 0; j < n; j++) {
  159.             c[i][j] = a[i][j]; // Построили матрицу в 1 степени, равную исходной
  160.         }
  161.     }
  162.  
  163.     for (k = 0; k < n; k++) {
  164.         for (i = 0; i < n; i++) {
  165.             for (j = 0; j < n; j++) {
  166.                 r = 16000;
  167.                 for (t = 0; t < n; t++) {
  168.                     if (c[i][t] + a[t][j] < r) { // Реализация формулы
  169.                         r = c[i][t] + a[t][j];
  170.                     }
  171.  
  172.                 }
  173.                 c[i][j] = r;
  174.             }
  175.         }
  176.     }
  177.  
  178. return c[number_start][number_end]; // Вывод длины пути из начальной точки в конечную
  179.  
  180. }
  181.  
  182. void main()
  183. {
  184.     struct stack *stk;
  185.     int elem;
  186.     int top;
  187.     int A[64][64], i, j, y1, y2, x1, x2, num_start, num_end, b[64], minway;
  188.     char word1, word2;
  189.     for (i = 0; i < 64; i++)
  190.         b[i] = 0;
  191.     init(stk);
  192.  
  193.     for (i = 0; i < 64; i++)
  194.     {
  195.         for (j = 0; j < 64; j++)
  196.             A[i][j] = 0;
  197.     }
  198.  
  199.  
  200.     for (i = 0; i < 64; i++)
  201.     {
  202.         for (j = 0; j < 64; j++)
  203.         {
  204.             if ((j == i + 10) || (j == i - 10) || (j == i + 6) || (j == i - 6) || (j == i + 15) || (j == i - 15) || (j == i + 17) || (j == i - 17))
  205.                 A[i][j] == 1;
  206.         }
  207.     }
  208.  
  209.     printf("Введите начальную клетку \n");
  210.     scanf_s("%c%i", &word1, &y1);
  211.     printf("Введите конечную клетку \n");
  212.     scanf_s("%c%i", &word2, &y2);
  213.     x1 = identity(word1);
  214.     x2 = identity(word2);
  215.     num_start = y1 * 8 + x1;
  216.     num_end = y2 * 8 + x2;
  217.     minway = search_minway(A[64][64], num_start, num_end);
  218.     func(num_start, num_end, minway, A[N][N], b[N], stk);
  219.     return;
  220. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top