Подсчет островов в матрице из файла - PullRequest
Новая
       26

Подсчет островов в матрице из файла

0 голосов
/ 27 августа 2018

поэтому у меня возникли проблемы с решением проблемы для моего IT-экзамена. enter image description here

Я решил это, и это частично сработало, но я мог найти решение только с использованием BFS, и я уверен, что для этого не требуются алгоритмы обхода графа, поскольку мы еще не сделали этого, но я не могу найти другое решение , Может ли кто-нибудь дать мне подсказку. Я опубликую код BFS, чтобы узнать, как я на самом деле это решил, а не то, как я думаю, что это должно было быть решено. 

#include <stdio.h>
#include <stdlib.h>
char file[20][20];
int v[20], ns, n, comp, c[20];
int prim;
int ultim;
FILE *f;
int nr = 0, nl, nc;

void matrix() {
  int i, j;
  char c, n;
  fscanf(f, "%d %d \n", &nl, &nc);
  for (i = 1; i <= nl; i++) {
    for (j = 1; j <= nc; j++) {
      c = getc(f);
      file[i][j] = c;
    }
    n = getc(f);
  }
}
// citirea grafului din fisier text si construirea matricei de adiacenta

// afisarea pe ecran a matricei de adiacenta

void afisare() {
  int i, j;
  printf("Matricea  : \n");

  for (i = 1; i <= nl; i++)

  {
    for (j = 1; j <= nc; j++)

      printf("%c", file[i][j]);

    printf("\n");
  }
}

// returnează primului nod nevizitat

int exista_nod_nevizitat(int v[20], int n) {
  int i, j;
  for (i = 1; i <= nl; i++)

    if (v[i] == 0)

      return i; // primul nod nevizitat

  return 0; // nu mai exista noduri nevizitate
}

// parcurgerea în latime a unei componente conexe, plecând din nodul de start ns

void parcurgere_latime(char file[20][20], int nl, int ns) {
  int i, j;
  comp++;

  v[ns] = 1;

  prim = ultim = 1;

  c[ultim] = ns;

  while (prim <= ultim) {
    for (i = 1; i <= nl; i++)

      if (file[c[prim]][i] == 'L')

        if (v[i] == 0)

        {
          ultim++;

          c[ultim] = i;

          v[i] = 1;
        }

    prim++;
  }
}

// functia principala main()

int main() {
  int set, nr;
  f = fopen("in1.txt", "r");

  fscanf(f, "%d \n", &set);
  while (set != 0) {
    matrix();
    afisare();

    while (exista_nod_nevizitat(v, n) != 0) {
      ns = exista_nod_nevizitat(v, n);

      parcurgere_latime(file, n, ns); // parcurg o alta componenta conexa
    }

    printf("Graful este alcătuit din ");
    printf("%d", comp);
    printf("componente conexe \n");

    set--;
  }
  return 0;
}

Ответы [ 2 ]

0 голосов
/ 27 августа 2018

Нашел это решение, которое кажется проще и быстрее 

int countIslands(char a[100][100])
{
    int count = 0;
    for ( i=0; i<nl; i++)
    {
        for (j=0; j<nc; j++)
        {
            if (a[i][j] == 'L')
            {
                if ((i == 0 || a[i-1][j] == '.') &&
                    (j == 0 || a[i][j-1] == '.'))
                    count++;
            }
        }
    }

    return count;
}
0 голосов
/ 27 августа 2018

Я напишу довольно простое решение, которое приходит на ум. Обратите внимание, что это не совсем не оптимально, и это немного грубый подход.

По сути, я думаю о том, чтобы пройти матричный элемент за элементом, и каждый раз, когда вы находите L (начало острова), находите его границы, переходя от соседа к соседу и отмечая его числом текущий остров, пока больше не будет соседей для элементов острова, затем продолжайте обход матрицы, повторяя те же шаги каждый раз, когда вы найдете L, которое не было отмечено.

...