查找所有相邻元素在C二维数组 [英] Finding all adjacent elements in a 2D array in C

问题描述

我的工作，其中在一个点上我坚持的一个项目。

I am working on a project where at one point I am stuck.

我的问题是，比如我有含3个不同的整数下面的二维数组。

My question is for example I have the following 2D array containing 3 different integers.

2 2 2 2 1 
1 2 2 2 1 
3 3 2 3 2 
3 1 3 3 1 
1 1 2 3 1 
1 3 1 3 3 

我要的是找到数组中包含的任何数量的阵中最长的相邻的元素链。

What i want is to find the longest adjacent elements chain of array of any number contained in the array.

像上面阵列最长链是数字2在

Like in the above array the longest chain is of digit 2.

2 2 2 2
  2 2 2
    2

谁能只是引导我为我有什么做的，实现这一目标？

Can anyone just guide me as to what I have to do to achieve this goal ?

感谢。

推荐答案

更​​容易吸引比解释...

Easier to draw than to explain...

2 2 2 2 1 => A A A A B => (A: 4, B: 1)
1 2 2 2 1 => C A A A B => (A: 3 + 4, B: 1 + 1, C: 1)
3 3 2 3 2 => D D A E F => (A: 1 + 7, B: 2, C: 1, D: 2, E: 1, F: 1)
3 1 3 3 1 => D G E E G => (A: 8, B: 2, C: 1, D: 2 + 1, E: 2 + 1, F: 1, G: 1)
1 1 2 3 1 => ...
1 3 1 3 3 => ...

更新

而现在，一些真正的code：

And now, with some real code:

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

#define ROWS 6
#define COLS 5

unsigned char eles[ROWS][COLS] = { { 2, 2, 2, 2, 1 }, 
                                   { 1, 2, 2, 2, 1 }, 
                                   { 3, 3, 2, 3, 2 }, 
                                   { 3, 1, 3, 3, 1 }, 
                                   { 1, 1, 2, 3, 1 }, 
                                   { 1, 3, 1, 3, 3 } };

struct zone {
  int acu;
  int row, col;
  int refs;
};

typedef struct zone zone;

zone *
new_zone(int row, int col) {
  zone *z = (zone *)malloc(sizeof(zone));
  z->col = col;
  z->row = row;
  z->refs = 1;
  z->acu = 0;
}

void croak (const char *str) {
  fprintf(stderr, "error: %s\n", str);
  exit(1);
}

void
free_zone(zone *z) {
  if (z->refs != 0) croak("free_zone: reference count is not cero");
  free(z);
}

zone *
ref_zone(zone *z) {
  z->refs++;
  return z;
}

void
unref_zone(zone *z) {
  z->refs--;
  if (!z->refs) free_zone(z);
}

int
main() {
  zone *last[COLS];
  zone *current[COLS];
  zone *best = new_zone(0, 0);
  int i, j;
  memset(last, 0, sizeof(last));

  for (j = 0; j < ROWS; j++) {
    for (i = 0; i < COLS; i++) {
      unsigned int ele = eles[j][i];
      zone *z;
      /* printf("analyzing ele: %d at row %d, col: %d\n", ele, j, i); */
      if (i && (ele == eles[j][i-1])) {
        /* printf("  equal to left element\n"); */
        z = ref_zone(current[i-1]);
        if (j && (ele == eles[j-1][i])) {
          zone *z1 = last[i];
          /* printf("  equal to upper element\n"); */
          if (z != z1) {
            int k;
            /* printf("  collapsing zone %p\n", z1); */
            z->acu += z1->acu;
            for (k = 0; k < COLS; k++) {
              if (last[k] == z1) {
                last[k] = ref_zone(z);
                unref_zone(z1);
              }
            }
            for (k = 0; k < i; k++) {
              if (current[k] == z1) {
                current[k] = ref_zone(z);
                unref_zone(z1);
              }
            }
          }
        }
      }
      else if (j && (ele == eles[j-1][i])) {
        /* printf("  equal to upper element\n"); */
        z = ref_zone(last[i]);
      }
      else {
        /* printf("  new element\n"); */
        z = new_zone(j, i);
      }
      z->acu++;
      current[i] = z;
      /* printf("  element zone: %p\n", z); */
    }
    for (i = 0; i < COLS; i++) {
      if (j) unref_zone(last[i]);
      last[i] = current[i];
      if (best->acu < current[i]->acu) {
        unref_zone(best);
        best = ref_zone(current[i]);
        /* printf("best zone changed to %p at row; %d, col: %d, acu: %d\n", best, best->row, best->col, best->acu); */
      }
    }
  }
  printf("best zone is at row: %d, col: %d, ele: %d, size: %d\n", best->row, best->col, eles[best->row][best->col], best->acu);
}

这篇关于查找所有相邻元素在C二维数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！