Counting islands in a matrix from file

Question

so I'm having trouble solving a problem for my IT exam.

I solved it and it partially worked but I could find a solution only using a BFS and I'm sure this doesn't require graph traversal algorithms since we haven't done them yet but I can't find any other solution. Could someone give me a hint.I'll post the BFS code down under just to how that I've actually solved this but not how I think it should've been solved.

#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;
}

Note that [trailing white space in `scanf()` formats](http://stackoverflow.com/questions/19499060/what-is-difference-between-scanfd-and-scanfd) cause trouble in general. It probably isn't harmful in your program, but should be avoid on principle. — Jonathan Leffler, Aug 27 '18 at 15:36
I don't think you need bfs. Maybe try a connected components approach. https://en.wikipedia.org/wiki/Connected-component_labeling — smac89, Aug 27 '18 at 15:38
You need to describe what your code is doing, then maybe you will receive some help — smac89, Aug 27 '18 at 15:42
Search starting at 'top left' corner, scanning across each row in turn. When you come across an `L`, you've got the top-most left-most corner of an island (but the rest of the island may be to the left of where you start, but will all be on the same line or below). Convert the `L` to another character (`@` for example). Now look around for connected `L`'s, converting each one to an `@` as it is part of the current island. When there are no more connected `L`'s, move onwards from where you started the current island, ignore any `@` markers and look for the next `L`. This avoids backtracking. — Jonathan Leffler, Aug 27 '18 at 15:46
I don't think the problem is well-formed if there are `L` or `T` shaped segments; I can make examples for which 2 or 3 is a valid decomposition into rectangles depending on the strategy. If we rule out touching rectangles, then it can be done by a single scan over the map, using a template that looks at the cur position, the element above and the one to the left while scanning right and down (as a simplification of Jonathan's solution above) — lockcmpxchg8b, Aug 27 '18 at 17:16
OT: when calling `fopen()`, always check (!=NULL) the returned value to assure the operation was successful, — user3629249, Aug 28 '18 at 06:18
OT: when calling any of the `scanf()` family of functions, including `fscanf()`, always check the returned value (not the parameter values) to assure the operation was successful. — user3629249, Aug 28 '18 at 06:20
variable names (and parameter names) should indicate `content` or `usage` (or better, both). Names like `v` `n` `f` `c`, etc are meaningless even in the current context — user3629249, Aug 28 '18 at 06:22

score 2 · Answer 1 · answered Aug 27 '18 at 15:51

2

Found this solution which seems to be easier and faster

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;
}

answered Aug 27 '18 at 15:51

Lola

218
1
11

Very nice solution, but wouldn't it count islands that are in an `L-shape` as one island? I believe the solution requires rectangles – smac89 Aug 27 '18 at 15:55
I think the `&&` should be changed to `||`, or handle the edge islands separately from the rest – smac89 Aug 27 '18 at 15:56

score 0 · Answer 2 · answered Aug 27 '18 at 15:49

I'll type out a pretty basic solution which comes to mind. Note that it is not certainly not optimal and is a bit of a brute-force approach.

Basically, what I'm thinking of is traversing the matrix element by element, and every time you find an L (beginning of the island), find its borders by going from neighbour to neighbour and marking it down with the number of the current island until there's no more neighbours for the elements of the island, then continue traversing the matrix, repeating the same steps every time you find an L that has not been marked.

Multumesc :)),am inteles pana la urma cum as putea sa o fac si am postat mai jos — Lola, Aug 27 '18 at 15:52

Counting islands in a matrix from file

2 Answers2