Das wichtige ist: Es spielt keine Rolle, ob die Vierecke, die daneben liegen, auf derselben Höhe liegen. Sie können auch versetzt weiter unten liegen und das sieht man hier - das funktioniert - natürlich!!!
Aber halt! Was so trivial klingt - ist es nicht!
Versetzt! Ja, das funktioniert ohne jedes Problem - das hat damit nichts zu tun! Weil der gesamte Raum daneben abgesucht wird!
Aber jetzt wird es spannend. Wenn etwas daneben liegt und etwas da drunter unter dem liegt, was daneben liegt, dann wird das gefunden. Weil das unter dem ersten liegt, neben dem das andere liegt! Nein, nicht deswegen. Das liegt dann zwar darunter! Aber! Das wird gefunden, weil es unter dem anderen liegt. Egal wie. Weil er sucht daneben ab, findet das daneben und unter diesem "daneben" findet er das "da drunter". Aber wenn eines unter dem liegt und neben dem eines liegt, dann findet er das neben, weil er da drunter ffindet und neben dem da drunter, das daneben. Aber nicht, weil das, was dem drunter liegt, unter dem ersten liegt - sondern, weil es neben dem da drunter liegt.
Was passiert aber jetzt - wenn wir eines haben, was weder nur drunter liegt noch daneben - sondern in der rechten unteren Ecke, während wir in der linken obere Ecke anfangen? Na ja, das hängt davon ab, ob eines drüber liegt oder eines drunter, was neben oder unter dem ersten liegt. Wenn da kein weiteres ist, unter dem das schräg untere ist, wird es nicht gefunden!
Es wäre also aus dieser Sicht zwigend notwendig, einen dritten bzw. - mit Schachtelung - vierten Aufruf zu machen, nämlich für die, die schräg drunter liegen, bei denen aber nichts drüber liegt und nichts daneben.
Aber spannend wird es erst jetzt! Wir versinnbildlichen uns das ganze aus der Sicht einer Programmiersprache. In einer Programmiersprache haben wir Schachtelungen
BEGIN A1
BEGIN A2
END A2
END A1
Und wir haben Sequenzen
A1; A2; A3; ...
Die Sequenzen werden über das ';' eingeleitet. Wenn wir das so sehen, gäbe es bei uns drei verschiedene Formen von ';'.
Nämlich 3 verschiedene Sequenzen: Daneben, Da drunter, schräg da drunter.
Das gibt es bei einer Programmiersprache, entweder man nennt es daneben oder da drunter, aber es ist einfach daneben, wenn man es daneben nennt.
Eigentlich könnten wir das auch zu unserem Prinzip einführen. Wenn wir Pakete haben, dann könnten wir diese auf dem Tisch ebenso gut nebeneinander legen, für uns käme das auf dasselbe raus.
Aber das tut das nicht. In unserem geometrischen Fall geht das nicht. Weil: Das gilt dann nicht mehr, wenn wir ein Paket packen, dann stellen wir uns automatisch vor, wir packen die Päckchen, die wir einpacken neben und hintereinander - im 2D-Raum.
Allerdings, wir können an den, der das Packet schnürt eine Anforderung stellen: Wer ein Paket so packt, dass ob in der nordwestlichen Ecke etwas sitzt und unten der süd-östlichen, der hat das Paket falsch gepackt. Das würde beim Transport durcheinander gehen. Deswegen muss der, der das Paket packt, die Pakete so packen, dass sie entweder nebeneinander gepackt sind, oder "hintereinander".
Und das hat jetzt auch funktioniert, mit da drunter.
#include <stdio.h>
#define PARSE_NO_ERR 0
#define PARSE_ERR -1
#define LEX_NO_SYM 1
#define LEX_NO_ERR 0
#define LEX_ERR_BAD_CHAR -2
#define LEX_ERR_WRONG_PARAMETER -3
#define LEX_ERR_BAD_TOKEN -4
#define WIDTH 512
#define HEIGHT 512
int lexer_width = 0;
int lexer_height = 0;
char bmp[HEIGHT][WIDTH] = {\
' ', ' ', ' ', ' ', ' ', ' ',\
' ', '#', '#', '#', '#', ' ',\
' ', '#', ' ', ' ', '#', ' ',\
' ', '#', ' ', ' ', '#', ' ',\
' ', '#', '#', '#', '#', ' ',\
' ', ' ', ' ', ' ', ' ', ' '};
int lexer(int a_limit_width, int a_limit_height, int b_limit_width, int b_limit_height, int c_limit_width, int c_limit_height, int d_limit_width, int d_limit_height, int *a_width, int *a_height, int *b_width, int *b_height, int *c_width, int *c_height, int *d_width, int *d_height);
int lexer(int a_limit_width, int a_limit_height, int b_limit_width, int b_limit_height, int c_limit_width, int c_limit_height, int d_limit_width, int d_limit_height, int *a_width, int *a_height, int *b_width, int *b_height, int *c_width, int *c_height, int *d_width, int *d_height) {
int i, j;
int k, l;
for (i = a_limit_height; i < d_limit_height; i++) {
for(j = a_limit_width; j < b_limit_width; j++) {
if ((bmp[i][j] != ' ') && (bmp[i][j] != '#'))
return LEX_ERR_BAD_CHAR;
if (bmp[i][j] == '#')
break;
}
if(bmp[i][j] == '#')
break;
}
if ((i == d_limit_height) && (j == b_limit_width))
return LEX_NO_SYM;
*a_height = i;
*a_width = j;
if (a_limit_height != b_limit_height)
return LEX_ERR_WRONG_PARAMETER;
if (b_limit_width <= a_limit_width)
return LEX_ERR_WRONG_PARAMETER;
for(k = *a_height, l = *a_width; l < b_limit_width; l++) {
if ((bmp[k][l] != ' ') && (bmp[k][l] != '#'))
return LEX_ERR_BAD_CHAR;
if (((k - 1) >= 0) && (l > (*a_width)) && (bmp[k][l+1] != ' ')) {
if (bmp[k-1][l] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k-1][l] != ' ')
return LEX_ERR_BAD_CHAR;
}
if (((k + 1) < (HEIGHT - 1)) && (l > (*a_width)) && (bmp[k][l+1] != ' ')) {
if (bmp[k+1][l] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k+1][l] != ' ')
return LEX_ERR_BAD_CHAR;
}
if (bmp[k][l+1] == ' ')
break;
}
*b_height = k;
*b_width = l;
if (c_limit_width != b_limit_width)
return LEX_ERR_WRONG_PARAMETER;
if (c_limit_height <= b_limit_height)
return LEX_ERR_WRONG_PARAMETER;
for(k = *b_height, l = *b_width; k < c_limit_height; k++) {
if ((bmp[k][l] != ' ') && (bmp[k][l] != '#'))
return LEX_ERR_BAD_CHAR;
if (((l - 1) >= 0) && (k > (*b_height)) && (bmp[k+1][l] != ' ')) {
if (bmp[k][l-1] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k][l-1] != ' ')
return LEX_ERR_BAD_CHAR;
}
if (((l + 1) < (WIDTH - 1)) && (k > (*b_height)) && (bmp[k+1][l] != ' ')) {
if (bmp[k][l+1] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k][l+1] != ' ')
return LEX_ERR_BAD_CHAR;
}
if (bmp[k+1][l] == ' ')
break;
}
*c_height = k;
*c_width = l;
if (d_limit_height != c_limit_height)
return LEX_ERR_WRONG_PARAMETER;
if (d_limit_width >= c_limit_width)
return LEX_ERR_WRONG_PARAMETER;
for(k = *c_height, l = *c_width; l >= d_limit_width; l--) {
if ((bmp[k][l] != ' ') && (bmp[k][l] != '#'))
return LEX_ERR_BAD_CHAR;
/* if (((k - 1) >= 0) && (l > (*d_width)) && (bmp[k][l-1] != ' ')) {
if (bmp[k-1][l] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k-1][l] != ' ')
return LEX_ERR_BAD_CHAR;
}
if (((k - 1) >= 0) && (l > (*d_width)) && (bmp[k][l-1] != ' ')) {
if (bmp[k+1][l] == '#')
return LEX_ERR_BAD_TOKEN;
if (bmp[k+1][l] != ' ')
return LEX_ERR_BAD_CHAR;
}*/
if (bmp[k][l-1] == ' ')
break;
}
*d_height = k;
*d_width = l;
if (a_limit_width != d_limit_width)
return LEX_ERR_WRONG_PARAMETER;
if (d_limit_height <= a_limit_height)
return LEX_ERR_WRONG_PARAMETER;
for(k = *d_height, l = *d_width; k >= a_limit_height; k--) {
if ((bmp[k][l] != ' ') && (bmp[k][l] != '#'))
return LEX_ERR_BAD_CHAR;
/* Bitte ergaenzen */
if (bmp[k-1][l] == ' ')
break;
}
return LEX_NO_ERR;
}
int parse(int a_limit_width, int a_limit_height, int b_limit_width, int b_limit_height, int c_limit_width, int c_limit_height, int d_limit_width, int d_limit_height) {
int a_width, a_height;
int b_width, b_height;
int c_width, c_height;
int d_width, d_height;
int retval;
int retval2 = PARSE_NO_ERR;
int retval3;
if ((retval = lexer(a_limit_width, a_limit_height, b_limit_width, b_limit_height, c_limit_width, c_limit_height, d_limit_width, d_limit_height, &a_width, &a_height, &b_width, &b_height, &c_width, &c_height, &d_width, &d_height)) == LEX_NO_SYM) {
return PARSE_NO_ERR;
}
else if (retval == LEX_NO_ERR) {
if ((a_width < (b_width - 5)) && \
(a_height < (c_height - 5)) && \
(a_height < (d_height - 5)) && \
(a_width < (c_width - 5)) && \
(b_height < (c_height - 5)) && \
(d_width < (c_width - 5))) {
retval3 = parse(a_width+2, a_height+2, b_width-2, b_height+2, c_width-2, c_height-2, d_width+2, d_height-2);
if (retval3 != PARSE_NO_ERR)
return PARSE_ERR;
}
/*if ((c_width > (c_limit_width + 2)) {
retval = parse(b_width+2, a_height, b_width, b_height, c_width, c_height, d_width-2, d_height+2);
if (retval != LEX_NO_ERR)
return PARSE_ERR;
}*/
if (b_width < b_limit_width) {
retval3 = parse(b_width+2, a_height, b_limit_width, b_height, c_limit_width, c_height, b_width+2, d_height);
if (retval3 != PARSE_NO_ERR)
return PARSE_ERR;
}
if (c_height < c_limit_height) {
retval3 = parse(a_width, d_height+2, b_width, d_height+2, c_width, c_limit_height, d_width, d_limit_height);
if (retval3 != PARSE_NO_ERR)
return PARSE_ERR;
}
}
if (retval == PARSE_NO_ERR) {
printf("%i %i %i %i\n", a_limit_height, a_limit_width, a_height, a_width);
printf("%i %i %i %i\n", b_limit_height, b_limit_width, b_height, b_width);
printf("%i %i %i %i\n", c_limit_height, c_limit_width, c_height, c_width);
printf("%i %i %i %i\n\n", d_limit_height, d_limit_width, d_height, d_width);
}
return retval2;
}
void print_data(void) {
int i, j;
for (i = 0; i < 15; i++) {
for (j = 0; j < 25; j++)
printf("%c", bmp[i][j]);
printf("\n");
}
}
void test_init(void) {
int i, j;
/*for(i = 0; i < HEIGHT; i++)
for(j = 0; j < WIDTH; j++)
bmp[i][j] = ' ';
bmp[28][28] = '#';*/
return;
}
void read_data (FILE *fp) {
int ch;
int i, j;
i = 0;
j = 0;
while (!feof(fp)) {
ch = fgetc(fp);
if (ch == '\n') {
while (j < WIDTH) {
bmp[i][j] = ' ';
j++;
}
j = 0;
i++;
}
else {
bmp [i][j] = ch;
j++;
}
}
for(; i < HEIGHT; i++)
for (j = 0; j < WIDTH; j++)
bmp [i][j] = ' ';
return;
}
int main(int argc, char *argv[]) {
int a_width, a_height;
int b_width, b_height;
int c_width, c_height;
int d_width, d_height;
FILE *fp;
if((fp = fopen(argv[1], "r")) == NULL) {
perror("Can't open file");
return -1;
}
read_data(fp);
print_data();
fclose(fp);
//test_init();
//lexer(0, 0, WIDTH, 0, WIDTH, HEIGHT, 0, HEIGHT, &a_width, &a_height, &b_width, &b_height, &c_width, &c_height, &d_width, &d_height);
if(parse(0, 0, WIDTH-1, 0, WIDTH-1, HEIGHT-1, 0, HEIGHT-1) == PARSE_NO_ERR)
printf("Kein Fehler");
else
printf("Fehler");
/*printf("a: %i %i\n", a_height, a_width);
printf("b: %i %i\n", b_height, b_width);
printf("c: %i %i\n", c_height, c_width);
printf("d: %i %i\n", d_height, d_width);*/
}
