SHARE
TWEET

Untitled

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