fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #define MAX_NUM 17
  5. typedef struct Square_tag Square;
  6. struct Square_tag {
  7.     char c;
  8.     int cost[MAX_NUM][MAX_NUM];
  9.     Square *ptr[MAX_NUM][MAX_NUM];
  10. };
  11. typedef struct {
  12.     Square *ary;
  13.     Square *start;
  14.     Square *goal;
  15.     int len_x;
  16.     int len_y;
  17. } SquareInfo;
  18. void get_pos(int len_x, int x, int y, int num, int *idx1, int *idx2) {
  19.     int x1, x2, y1, y2;
  20.     switch (num) {
  21.         case 0: x1 = -1; y1 = -1; x2 = 0; y2 = -1; break;
  22.         case 1: x1 = 1; y1 = 1; x2 = 0; y2 = 1; break;
  23.         case 2: x1 = 1; y1 = -1; x2 = 0; y2 = -1; break;
  24.         case 3: x1 = -1; y1 = 1; x2 = 0; y2 = 1; break;
  25.         case 4: x1 = -1; y1 = -1; x2 = -1; y2 = 0; break;
  26.         case 5: x1 = 1; y1 = 1; x2 = 1; y2 = 0; break;
  27.         case 6: x1 = -1; y1 = 1; x2 = -1; y2 = 0; break;
  28.         case 7: x1 = 1; y1 = -1; x2 = 1; y2 = 0; break;
  29.         case 8: x1 = 0; y1 = 0; x2 = 0; y2 = -1; break;
  30.         case 9: x1 = 0; y1 = 0; x2 = 0; y2 = 1; break;
  31.         case 10: x1 = 0; y1 = 0; x2 = -1; y2 = 0; break;
  32.         case 11: x1 = 0; y1 = 0; x2 = 1; y2 = 0; break;
  33.         case 12: x1 = 0; y1 = -1; x2 = 0; y2 = 0; break;
  34.         case 13: x1 = 0; y1 = 1; x2 = 0; y2 = 0; break;
  35.         case 14: x1 = -1; y1 = 0; x2 = 0; y2 = 0; break;
  36.         case 15: x1 = 1; y1 = 0; x2 = 0; y2 = 0; break;
  37.         default: x1 = 0; y1 = 0; x2 = 0; y2 = 0; break;
  38.     }
  39.     *idx1 = ((y + y1) * len_x) + (x + x1);
  40.     *idx2 = ((y + y2) * len_x) + (x + x2);
  41. }
  42. int get_direction(int num, int from) {
  43.     int direction;
  44.     switch (num) {
  45.         case 0: case 2: case 8: case 12: direction = (from) ? 0 : 1; break;
  46.         case 1: case 3: case 9: case 13: direction = (from) ? 1 : 0; break;
  47.         case 4: case 6: case 10: case 14: direction = (from) ? 2 : 3; break;
  48.         case 5: case 7: case 11: case 15: direction = (from) ? 3 : 2; break;
  49.         default: direction = -1;
  50.     }
  51.     return direction;
  52. }
  53. int get_cost(int num) {
  54.     int cost;
  55.     if (num < 12) {
  56.         cost = 2;
  57.     } else if (num < 16) {
  58.         cost = 1;
  59.     } else {
  60.         cost = 0;
  61.     }
  62.     return cost;
  63. }
  64. void print_square(SquareInfo *info) {
  65.     Square *ary;
  66.     int i_x, i_y, idx;
  67.     ary = info->ary;
  68.     for (i_y = 1; i_y < (info->len_y - 1); i_y++) {
  69.         for (i_x = 1; i_x < (info->len_x - 1); i_x++) {
  70.         	idx = (i_y * info->len_x) + i_x;
  71.             putchar(ary[idx].c);
  72.         }
  73.         puts("");
  74.     }
  75. }
  76. int scan_square(SquareInfo *info, int *cost_p) {
  77.     Square *ary, *ptr, *goal;
  78.     int len_x, len_y, i_x, i_y, i_from, i_to, i_from_rev, i_to2, idx;
  79.     int min_cost, max_cost, change, cost, add_cost;
  80.     ary = info->ary;
  81.     goal = info->goal;
  82.     len_x = info->len_x;
  83.     len_y = info->len_y;
  84.     min_cost = 0x7FFFFFFF;
  85.     max_cost = -1;
  86.     change = 0;
  87.     for (i_y = 1; i_y < (len_y - 1); i_y++) {
  88.         for (i_x = 1; i_x < (len_x - 1); i_x++) {
  89.             idx = (i_y * len_x) + i_x;
  90.             for (i_from = 0; i_from < MAX_NUM; i_from++) {
  91.                 for (i_to = 0; i_to < MAX_NUM; i_to++) {
  92.                 	cost = ary[idx].cost[i_from][i_to];
  93.                     if (cost > 0) {
  94.                         if ((&ary[idx] == goal) && (min_cost > cost)) min_cost = cost;
  95.                         if ((&ary[idx] == goal) && (max_cost < cost)) max_cost = cost;
  96.                     	i_from_rev = ((i_from % 2) > 0) ? (i_from - 1) : (i_from + 1);
  97.                     	ptr = ary[idx].ptr[i_from][i_to];
  98.                     	for (i_to2 = 0; i_to2 < MAX_NUM; i_to2++) {
  99.                             if (ptr && get_direction(i_from_rev, 1) != get_direction(i_to2, 2) && ptr->cost[i_from_rev][i_to2] == 0) {
  100.                                 add_cost = get_cost(i_to2);
  101.                                 ptr->cost[i_from_rev][i_to2] = cost + add_cost;
  102.                                 if ((ptr == goal) && (min_cost > (cost + add_cost))) min_cost = cost + add_cost;
  103.                                 if ((ptr == goal) && (max_cost < (cost + add_cost))) max_cost = cost + add_cost;
  104.                                 change++;
  105.                             }
  106.                         }
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.     }
  112.     //printf("change=%d min_cost=%d max_cost=%d \n", change, min_cost, max_cost);
  113.     *cost_p = min_cost;
  114.     return change;
  115. }
  116. void create_square(int argc, char *argv[], SquareInfo *info) {
  117.     Square *ary;
  118.     int i, len, len_x, len_y, i_x, i_y, idx, sizeof_ary;
  119.     int i_from, i_to, idx1, idx2, idx3, idx4, cost;
  120.     char c;
  121.     len_x = 0;
  122.     for (i = 1; i < argc; i++) {
  123.         len = strlen(argv[i]);
  124.         if (len_x < len) len_x = len;
  125.     }
  126.     len_x += 2;
  127.     len_y = (argc - 1) + 2;
  128.     sizeof_ary = len_y * len_x * sizeof(Square);
  129.     ary = malloc(sizeof_ary);
  130.     memset(ary, 0, sizeof_ary);
  131.     //printf("len_x=%d len_y=%d sizeof_ary=%d \n", len_x, len_y, sizeof_ary);
  132.     for (i_y = 0; i_y < len_y; i_y++) {
  133.         for (i_x = 0; i_x < len_x; i_x++) {
  134.         	idx = (i_y * len_x) + i_x;
  135.         	len = (i_y > 0 && i_y < (len_y - 1)) ? (strlen(argv[i_y]) + 1) : 0;
  136.             c = (i_x > 0 && i_x < len) ? argv[i_y][i_x - 1] : '#';
  137.             ary[idx].c = c;
  138.             if (c == 'S') info->start = &ary[idx];
  139.             if (c == 'G') info->goal = &ary[idx];
  140.         }
  141.     }
  142.     for (i_y = 0; i_y < (len_y - 1); i_y++) {
  143.         for (i_x = 0; i_x < (len_x - 1); i_x++) {
  144.             idx = (i_y * len_x) + i_x;
  145.             for (i_from = 0; i_from < MAX_NUM; i_from++) {
  146.                 get_pos(len_x, i_x, i_y, i_from, &idx1, &idx2);
  147.                 for (i_to = 0; i_to < MAX_NUM; i_to++) {
  148.                     if (get_direction(i_from, 1) == get_direction(i_to, 0) || ary[idx].c == '#') {
  149.                        cost = -1;
  150.                     } else {
  151.                         get_pos(len_x, i_x, i_y, i_to, &idx3, &idx4);
  152.                         if (ary[idx1].c != '#' && ary[idx2].c != '#' && ary[idx3].c != '#' && ary[idx4].c != '#') {
  153.                             if (ary[idx1].c == 'S') {
  154.                                 cost = get_cost(i_from);
  155.                                 cost += get_cost(i_to);
  156.                             } else {
  157.                                 cost = 0;
  158.                             }
  159.                         } else {
  160.                             cost = -1;
  161.                         }
  162.                     }
  163.                     ary[idx].cost[i_from][i_to] = cost;
  164.                     if (cost >= 0) ary[idx].ptr[i_from][i_to] = &ary[idx3];
  165.                 }
  166.             }
  167.         }
  168.     }
  169.     info->ary = ary;
  170.     info->len_x = len_x;
  171.     info->len_y = len_y;
  172. }
  173. int main_part11_270(int argc, char *argv[]) {
  174.     SquareInfo info;
  175.     int cost = -1;
  176.     create_square(argc, argv, &info);
  177.     print_square(&info);
  178.     while (scan_square(&info, &cost));
  179.     printf("=> %d \n", cost);
  180.     return 0;
  181. }
  182. int main(int argc, char *argv[]) {
  183.     char *argv1[] = {"", "S....", "#....", "..#..", "....G"};
  184.     char *argv2[] = {"", "S.....G", "......."};
  185.     if (argc <= 1) {
  186.         main_part11_270(sizeof(argv1) / sizeof(char*), argv1);
  187.         main_part11_270(sizeof(argv2) / sizeof(char*), argv2);
  188.     } else {
  189.         main_part11_270(argc, argv);
  190.     }
  191.     return 0;
  192. }
  193.  
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
S....
#....
..#..
....G
=> 9 
S.....G
.......
=> 12
https://ideone.com/YLAnLJ
language:
C (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!