Как соединить головоломки так, чтобы правый край имел такую ​​же длину, как левый край другой головоломки?

Question

У меня есть пазлы, которые выглядят так:

    === ==== 
=== ===
    === ====

Левый край имеет длину от 0 до 10 000, а справа также средняя часть от 1 до 10 000. Поэтому вопрос в том, могу ли я построить Прямоугольник? как первая головоломка имеет длину левого края, равную 0, а последняя головоломка имеет правый край длины 0, а посередине они идеально подходят?

Мне дано количество головоломок, которые у меня есть, и их параметры такие:

6
1 9 2
0 3 1
0 4 1
8 9 0
2 9 0
1 5 0

и результат может быть любым из этого:

2
0 3 1
1 5 0

или

3
0 3 1
1 9 2
2 9 0

или

2
0 4 1
1 5 0

Но если есть без результата мне нужно printf("no result")

Я должен сделать это в C, я подумал о создании некоторого дерева и поиске его с помощью BFS, где вершины будут иметь длину ребер, а ребро будет иметь среднюю длину и когда достигнуто 0 я бы набрал go весь путь и собирал числа, но это трудно кодировать. Поэтому я решил сделать рекурсию, но я также застрял:

#include<stdio.h>

int main(){

    int a;
    scanf("%d", &a);//here i get how many puzzles i have
    int tab[a][3];//array for puzzles
    int result[][3];//result array
    int k = 0;//this will help me track how many puzzles has my result array

    for(int i = 0; i < a; i++){//upload puzzles to array
        for(int j = 0; j < 3; j++){
            scanf("%d", &tab[i][j]);
        }
    }

    findx(0, a, tab, result, k);//start of recursion, because start has to be length 0

}
int findx(int x, int a, int *tab[], int *result[], int k){//i am looking for puzzle with length x on start
    for(int i = 0; i < a; i++){
        if(tab[a][0] == x){//there i look for puzzles with x length at start
            if(tab[a][2] == 0){//if i find such puzzle i check if this is puzzle with edge length zero at the end
                for(int m = 0; m < 3; m++){//this for loop add to my result array last puzzle
                    result[k][m] = tab[a][m];
                }
                return print_result(result, k);//we will return result go to print_result function
            }
            else{//if i have puzzle with x length on the left and this is not puzzle which ends rectangle i add this puzzle
                    //to my result array and again look for puzzle with x equal to end length of puzzle i found there
                for(int m = 0; m < 3; m++){
                    result[k][m] = tab[a][m];
                    k += 1;
                }
                findx(tab[a][2], a, tab, result, k);
            }
        }
    }
    printf("no result");
}

int print_result(int *result[], int k){
    printf("%d", &k);//how many puzzles i have
    printf("\n");
    for(int i = 0; i < k; i++){//printing puzzles...
        for(int j = 0; j < 3; j++){
            printf("%d ", &result[i][j]);
        }
        printf("\n");//...in separate lines
    }
}

У меня есть ошибка, что массив результатов не может выглядеть так int result[][3] из-за [], но я не знаю, сколько головоломки, которые я собираюсь использовать так? ... и у меня есть неявное объявление для обеих моих функций. Ребята, помогите, я не очень разбираюсь в C, и решить эту проблему очень сложно.

Answer 1

#include<stdio.h>

void findx(int x, int a, int tab[a][3], int result[200000][3], int puzzlesinresult) { //i am looking for puzzle with length x on start
  for (int i = 0; i < a; i++) {
    if (tab[i][0] == x) { //there i look for puzzles with x length at start
      if (tab[i][2] == 0) { //if i find such puzzle i check if this is puzzle with edge length zero at the end
        for (int m = 0; m < 3; m++) { //this for loop add to my result array last puzzle
          result[puzzlesinresult][m] = tab[i][m];
        }
        return print_result(result, puzzlesinresult); //we will return result go to print_result function
      } else { //if i have puzzle with x length on the left and this is not puzzle which ends rectangle i add this puzzle
        //to my result array and again look for puzzle with x equal to end length of puzzle i found there
        while (result[puzzlesinresult - 1][2] != tab[i][0] && puzzlesinresult > 0) {
          puzzlesinresult -= 1;
        }
        int isusedpuzzle = 0;
        for (int j = 0; j < puzzlesinresult; j++) {
          if (result[j][0] == tab[i][0] && result[j][1] == tab[i][1] && result[j][2] == tab[i][2]) {
            isusedpuzzle = 1;
          } else {
            //pass
          }
        }
        if (isusedpuzzle == 0) {
          for (int m = 0; m < 3; m++) {
            result[puzzlesinresult][m] = tab[i][m];
          }
          puzzlesinresult += 1;
          findx(tab[i][2], a, tab, result, puzzlesinresult);
        }
      }
    }
  }
}

void print_result(int result[200000][3], int puzzlesinresult) {
  printf("%d\n", puzzlesinresult + 1); //how many puzzles i have
  for (int i = 0; i < puzzlesinresult + 1; i++) { //printing puzzles...
    for (int j = 0; j < 3; j++) {
      printf("%d ", result[i][j]);
    }
    printf("\n"); //...in separate lines
  }
  exit(0);
}

int main() {

  int a;
  scanf("%d", & a); //here i get how many puzzles i have
  int tab[a][3]; //array for puzzles
  int result[100][3]; //result array
  int puzzlesinresult = 0; //this will help me track how many puzzles has my result array

  for (int i = 0; i < a; i++) { //upload puzzles to array
    for (int j = 0; j < 3; j++) {
      scanf("%d", & tab[i][j]);
    }
  }
  for (int i = 0; i < a; i++) { //here i delete puzzles that doesnt contribute anything like 1 x 1,2 x 2,..
    if (tab[i][0] == tab[i][2] && tab[i][0] != 0) {
      for (int p = i; p < a; p++) {
        for (int j = 0; j < 3; j++) {
          tab[p][j] = tab[p + 1][j];
        }
      }
    }
  }

  findx(0, a, tab, result, puzzlesinresult); //start of recursion, because start has to be length 0
  printf("NONE");
}

Возвращает иногда правильный результат. Если вы обнаружите, что эта программа не работает, я с удовольствием поделюсь с вами этими случаями:)

Answer 2

Я не уверен, что понимаю общую логику c проблемы, но вам определенно нужны контейнеры переменного размера для вкладки И AND результата. Массивы имеют фиксированный размер и должны быть определены во время компиляции. Следующее должно по крайней мере компилироваться без предупреждений:

#include<stdio.h>
#include<stdlib.h>

void print_result(int (*result)[3], int k){
    printf("%d", k);//how many puzzles i have
    printf("\n");
    for(int i = 0; i <= k; i++){//printing puzzles...
        for(int j = 0; j < 3; j++){
            printf("%d ", result[i][j]);
        }
        printf("\n");//...in separate lines
    }
}

void findx(int x, int a, int (*tab)[3], int (*result)[3], int k){//i am looking for puzzle with length x on start
    for(int i = 0; i < a; i++){
        if(tab[i][0] == x){//there i look for puzzles with x length at start
            if(tab[i][2] == 0){//if i find such puzzle i check if this is puzzle with edge length zero at the end
                for(int m = 0; m < 3; m++){//this for loop add to my result array last puzzle
                    result[k][m] = tab[i][m];
                }
                print_result(result, k);//we will return result go to print_result function
                return;
            }
            else{//if i have puzzle with x length on the left and this is not puzzle which ends rectangle i add this puzzle
                    //to my result array and again look for puzzle with x equal to end length of puzzle i found there
                for(int m = 0; m < 3; m++){
                    result[k][m] = tab[i][m];
                    k += 1;
                    ///** Increase size of result **/
                    //int (*newptr)[3] = realloc(result, (k+1) * sizeof(int[3]));
                    //if (newptr)
                    //    result = newptr;
                }
                findx(tab[i][2], a, tab, result, k);
            }
        }
    }
    printf("no result\n");
}

int main(){

    int a;
    scanf("%d", &a);//here i get how many puzzles i have
    int (*tab)[3] = malloc(a * sizeof(int[3]));//array for puzzles
    int (*result)[3] = malloc(a * sizeof(int[3]));//array for puzzles

    int k = 0;//this will help me track how many puzzles has my result array

    for(int i = 0; i < a; i++){//upload puzzles to array
        for(int j = 0; j < 3; j++){
            scanf("%d", &tab[i][j]);
        }
    }

    findx(0, a, tab, result, k);//start of recursion, because start has to be length 0

}

Обратите внимание, что я изменил вкладку и типы результатов на (*int)[3]. Из-за порядка операций нам нужны круглые скобки здесь. Поскольку они имеют переменный размер, они требуют динамического распределения памяти c. В интересах краткости и читабельности я не проверял возвращаемые значения malloc или realloc. На практике вы должны убедиться, что возвращаемый указатель не является NULL. Поскольку мы используем динамическое распределение памяти c, мы также должны использовать free, если вы планируете делать что-то еще с этой программой. В противном случае это не имеет большого значения, потому что выход из программы все равно освободит ресурсы. Вы на самом деле не хотите освобождать. поскольку мы передаем указатель по значению на findx и realloc может изменить адрес, он может вернуться с другим адресом. Кроме того, обратите внимание, что мне нужно include <stdlib.h> для динамического c выделения памяти.

Дополнительные вопросы

Ваши функции print_results и findx не объявляется, когда вы звоните им в main. Ваша функция должна быть выше основной или иметь «прототипы функций» выше main.

В printf s вам не нужны &. Вы не хотите отправлять адрес переменной на printf. Вы хотите отправить то, что на самом деле будет напечатано.

И что теперь?

Программа по-прежнему не дает правильных результатов. Он просто выводит 0 как результат каждый раз. Это должно по крайней мере дать вам отправную точку. Изменив эту строку в print_results:

for(int i = 0; i < k; i++){//printing puzzles...

на

for(int i = 0; i <= k; i++){//printing puzzles...

я по крайней мере смог вывести 0 0 0. Это кажется более правильным, потому что если k равно 0, мы вообще не l oop.