fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. typedef struct {
  6.     int size;
  7.     int len;
  8.     char *v;
  9. } Vector;
  10.  
  11. static void v_free(Vector *v) {
  12.     free(v->v);
  13.     free(v);
  14. }
  15.  
  16. static Vector *v_new(char size) {
  17.     Vector *v = calloc(1, sizeof(*v));
  18.     v->size = size;
  19.     v->v = calloc(size, sizeof(char));
  20.     return v;
  21. }
  22.  
  23. static void v_resize(Vector *v, int size) {
  24.     v->v = realloc(v->v, sizeof(int) * size);
  25.     v->size = size;
  26. }
  27.  
  28. static void v_push(Vector *v, int elem) {
  29.     if (v->len >= v->size) {
  30.         v_resize(v, v->size * 2);
  31.     }
  32.     v->v[v->len++] = elem;
  33. }
  34.  
  35. static int v_len(Vector *v) {
  36.     return v->len;
  37. }
  38.  
  39. static void v_print(Vector *v) {
  40.     for (int i = 0; i < v->len; i++) {
  41.         printf("%c", v->v[i]);
  42.     }
  43.     printf("\n");
  44. }
  45.  
  46. static char v_get(const Vector *v, int i) {
  47.     if (i < 0 || i >= v->len) {
  48.         return '\0';
  49.     }
  50.     return v->v[i];
  51. }
  52.  
  53. static void v_set(Vector *v, int i, char ch) {
  54.     v->v[i] = ch;
  55. }
  56.  
  57. typedef struct {
  58.     int size;
  59.     int len;
  60.     Vector **rows;
  61. } Matrix;
  62.  
  63. static void m_free(Matrix *m) {
  64.     for (int i = 0; i < m->len; i++) {
  65.         Vector *v = m->rows[i];
  66.         v_free(v);
  67.     }
  68.     free(m->rows);
  69.     free(m);
  70. }
  71.  
  72. static Matrix *m_new(int size) {
  73.     Matrix *m = calloc(1, sizeof(*m));
  74.     m->size = size;
  75.     m->rows = calloc(size, sizeof(Vector *));
  76.     return m;
  77. }
  78.  
  79. static void m_resize(Matrix *m, int size) {
  80.     m->rows = realloc(m->rows, sizeof(Vector *) * size);
  81.     m->size = size;
  82. }
  83.  
  84. static void m_push(Matrix *m, Vector *v) {
  85.     if (m->len >= m->size) {
  86.         m_resize(m, m->size * 2);
  87.     }
  88.     m->rows[m->len++] = v;
  89. }
  90.  
  91. static void m_print(const Matrix *m) {
  92.     for (int i = 0; i < m->len; i++) {
  93.         Vector *v = m->rows[i];
  94.         v_print(v);
  95.     }
  96. }
  97.  
  98. static int m_len_rows(const Matrix *m) {
  99.     return m->len;
  100. }
  101.  
  102. static int m_len_cols(const Matrix *m) {
  103.     if (m->len <= 0) {
  104.         return -1;
  105.     }
  106.     return v_len(m->rows[0]);
  107. }
  108.  
  109. static char m_get(const Matrix *m, int r, int c) {
  110.     return v_get(m->rows[r], c);
  111. }
  112.  
  113. static void m_set(Matrix *m, int r, int c, char ch) {
  114.     Vector *v = m->rows[r];
  115.     v_set(v, c, ch);
  116. } 
  117.  
  118. static bool dfs(Matrix *m, int total, int sr, int sc, int dep) {
  119.     static int dx[] = {-1, 0, 1, 0};
  120.     static int dy[] = {0, -1, 0, 1};
  121.     int r = m_len_rows(m);
  122.     int c = m_len_cols(m);
  123.     if (total == dep) {
  124.         return true;
  125.     }
  126.  
  127.     for (int k = 0; k < 4; k++) {
  128.         int r2 = sr + dy[k];
  129.         int c2 = sc + dx[k];
  130.         if (r2 < 0 || r2 >= r || c2 < 0 || r2 >= c) {
  131.             continue;
  132.         }
  133.         if (m_get(m, r2, c2) != '0') {
  134.             continue;
  135.         }
  136.         m_set(m, r2, c2, '2');
  137.         if (dfs(m, total, r2, c2, dep + 1)) {
  138.             return true;
  139.         }
  140.         m_set(m, r2, c2, '0');
  141.     }
  142.  
  143.     return false;
  144. }
  145.  
  146. int main(void) {
  147.     int r, c;
  148.  
  149.     for (;;) {
  150.         if (scanf("%d %d\n", &r, &c) == EOF) {
  151.             break;
  152.         }
  153.  
  154.         Matrix *m = m_new(r);
  155.         int total = 0, sr = 0, sc = 0;
  156.  
  157.         for (int i = 0; i < r; i++) {
  158.             Vector *v = v_new(c);
  159.             for (int j = 0; j < c; j++) {
  160.                 char ch = fgetc(stdin);
  161.                 v_push(v, ch);
  162.                 if (ch == '0') {
  163.                     total++;
  164.                 } else if (ch == '2') {
  165.                     sr = i;
  166.                     sc = j;
  167.                 }
  168.             }
  169.             fgetc(stdin); // \n
  170.             m_push(m, v);
  171.         }
  172.         fgetc(stdin); // \n
  173.  
  174.         m_print(m);
  175.         if (dfs(m, total, sr, sc, 0)) {
  176.             puts("OK");
  177.         } else {
  178.             puts("NG");
  179.         }
  180.         puts("");
  181.  
  182.         m_free(m);
  183.     }
  184.  
  185.     return 0;
  186. }
Success #stdin #stdout 0s 5556KB
comments (?)
stdin
copy 
4 4
0000
0210
0000
0100

4 4
0000
0200
0010
0000

5 6
000000
210000
000100
000001
000000

5 6
000000
210000
000100
000000
000001
stdout
copy 
0000
0210
0000
0100
OK

0000
0200
0010
0000
NG

000000
210000
000100
000001
000000
OK

000000
210000
000100
000000
000001
NG
https://ideone.com/1427CY
language:
C (gcc 8.3)
created:
2 years ago
visibility:
public

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!