我正在做一个项目,有时我被卡住了.
我的问题是例如我有以下2D数组包含3个不同的整数.
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
我想要的是找到数组中包含的任何数字的数组的最长的相邻元素链.
与上面的数组一样,最长的链是数字2.
2 2 2 2 2 2 2 2
任何人都可以指导我为实现这一目标必须做些什么吗?
谢谢.
解决方法
绘制比解释更容易…
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,D: 2 + 1,E: 2 + 1,F: 1,G: 1) 1 1 2 3 1 => ... 1 3 1 3 3 => ...
更新:
现在,有了一些真正的代码:
#include <stdlib.h> #include <string.h> #include <stdio.h> #define ROWS 6 #define COLS 5 unsigned char eles[ROWS][COLS] = { { 2,2,1 },{ 1,{ 3,3,2 },1,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,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,ele: %d,size: %d\n",eles[best->row][best->col],best->acu); }